900
-8883552 -8024557 -7378030 -7387931 -6790063 -6671637 -6140828 -5285016 -5279170 -5238301 -4772182 -4632835 -4203516 -4255711 -4107208 -3652870 -2762917 -1815193 -1459123 -1049700 -79059 -21462013 -20484857 -19498022 -18811571 -17880697 -17011217 -17070443 -17052041 -16407904 -15997418 -15268830 -14346902 -13861889 -13273840 -12326323 -11836296 -11554769 -10807504 -10617456 -10007972 -9141857 -28986056 -28111538 -27383032 -26695262 -25875917 -25756972 -25337802 -24882212 -24937294 -24528410 -24302587 -24398130 -23722440 -23287026 -23237403 -22712658 -22788608 -22504507 -22502394 -22305375 -21479220 -38940432 -38572351 -37631520 -36949951 -36466515 -36141992 -36023049 -36003465 -35105442 -34225891 -33511758 -33434378 -32762717 -32573638 -32519847 -31681523 -31692228 -31173805 -30802761 -30255705 -29483498 -45632067 -45494974 -44853640 -43962190 -43784980 -43675560 -42777722 -42664200 -42635439 -41846761 -41321462 -41010240 -40965877 -40989902 -40812404 -40568865 -40602230 -40282367 -39456573 -38958206 -38997648 -52946201 -52898941 -52447041 -51531112 -51599583 -51221535 -51237743 -50891666 -50081620 -50012652 -50116551 -49405458 -48541067 -48630941 -48075017 -47921652 -47316350 -47230349 -47122216 -47195187 -46365753 -63657629 -63051874 -62289204 -62285213 -61765376 -61835616 -61501883 -60728032 -60839043 -59925781 -58951805 -58516706 -57807785 -56964897 -56342898 -55855242 -55506426 -55162518 -54406085 -53916688 -53706706 -72913750 -72718289 -71991808 -71090725 -70909634 -70167068 -69913637 -69099362 -68589877 -67965002 -68027145 -67279448 -66599491 -66636817 -66525911 -65559432 -65148152 -65133832 -64602772 -64555415 -64652800 -85729258 -85358702 -84460688 -83814998 -82870421 -82051411 -81403471 -80607293 -80262776 -79505877 -79135277 -78285171 -77641832 -77396688 -76913742 -76653301 -76418828 -75751836 -74784508 -73840249 -73043841 -91405966 -91462418 -91438275 -91024617 -90502395 -90549039 -90457206 -90021084 -90114286 -89990976 -89688339 -89793530 -89812259 -89390561 -89163312 -88719479 -87888030 -86895066 -86858995 -86177396 -85801364 -101797278 -101487857 -100886506 -100266311 -99857048 -98883840 -98113294 -97592935 -97075373 -96185036 -95366665 -94773694 -94330567 -94035739 -93656568 -93052446 -92866728 -92496060 -91943008 -91865812 -91354935 -110894064 -110698367 -109727863 -109168221 -108878220 -108354806 -107357188 -107426529 -106478384 -106117993 -105848858 -105292889 -105071133 -104521386 -104059990 -103744043 -103477797 -103416648 -102785162 -101950117 -101873767 -120485998 -119683565 -118796322 -118476472 -117646579 -117336846 -117020191 -116670601 -116579498 -116688707 -116654596 -116681270 -116498626 -115602357 -114640767 -114154353 -114215044 -113413742 -113060565 -112478649 -111789884 -130840423 -129941870 -129669687 -129505090 -129530663 -128671846 -128005719 -127115659 -126889588 -126501568 -126416309 -125585476 -124924904 -124568184 -124490615 -123543256 -123495807 -123395034 -122548364 -121729926 -121234037 -141363145 -141242090 -140507877 -139849537 -139010261 -138579510 -138273884 -138037005 -137414454 -136965237 -136600938 -136303119 -135593525 -135406744 -134446968 -134514324 -133549017 -132549303 -132387337 -132158919 -131548338 -148008442 -147594198 -147680243 -147686217 -147623225 -147169495 -146325213 -145895865 -145522247 -144574218 -143996345 -144073581 -144167240 -144203095 -143303340 -142869791 -142808106 -142539340 -141786459 -141750314 -141606322 -157301443 -156308395 -156407786 -156301323 -155842461 -155846548 -155435971 -155382996 -154861860 -154132671 -153674098 -153175046 -152518058 -151900924 -151338070 -150635347 -149902388 -149441920 -148660324 -148203373 -147927964 -167117678 -166154741 -165899397 -165222934 -164616385 -164041452 -163360509 -162740563 -162584746 -161918818 -161973474 -161447697 -160491945 -159997855 -159870416 -159614601 -159541669 -159610878 -159094829 -158880786 -157900525 -176648740 -176025643 -175824644 -175769033 -175195574 -174645931 -174054194 -173100273 -172928066 -172705555 -172249896 -171690284 -170789280 -169975933 -170085488 -170092667 -169625933 -169566971 -168703741 -168579029 -167998938 -185056598 -184374808 -183737152 -183716290 -182963270 -182365028 -182300634 -181895550 -181851495 -181100125 -180313479 -180308962 -180245375 -179764523 -179303605 -178312687 -178105387 -178109967 -177148802 -177064929 -176979266 -194041806 -193799018 -193632438 -193427906 -193492814 -193177116 -192441983 -191684383 -191328003 -191137913 -190882095 -190240291 -189611702 -189262312 -188279369 -188001663 -187618026 -186985437 -186404361 -186400701 -185529696 -196921128 -196748800 -196310280 -196419474 -195702760 -194777992 -194887673 -194628928 -194012161 0 759225 701881 689038 1409922 2307379 2712904 3500191 3724590 3974203 4254231 4669320 4917378 5051809 5697668 6611855 6853284 7716439 8547512 8765328 9026013 9826281 10117341 10730312 11261187 11213143 11306892 11617827 11756561 11893497 12017885 11974672 12090361 13055695 13696453 14519866 15443012 15778718 15715283 16409524 17018210 16910307 17708173 18410573 18745180 19131454 20075221 19999619 20162852 20554127 21273811 21361688 21929652 22665321 23550499 24006854 24101746 24052383 24993019 25418366 26103565 26381737 26932390 27445831 28200176 28498733 29445044 30113794 31105220 31146258 31790219 32361927 32493687 33032342 33856714 34659702 34837415 34739951 34842068 35647120 35625718 36439389 37101751 37349435 37544015 38062992 38559935 39132941 39687990 39869868 39780601 40425089 40417010 40981009 41938799 42696680 43592099 44590944 44727418 45592253 45964241 46791065 47725436 48314312 48282692 48195630 48846159 49128967 50060661 50640567 50730929 51588894 51587879 52187474 52513887 52419726 52613197 52600707 53140496 53944871 54471891 55404477 55542259 55476440 56243111 56242388 56499804 56998565 57157796 57360799 57541499 58282601 58631808 58733084 59355795 60225662 60407902 60720147 60666942 61186341 62099473 62854935 63709396 64614026 64532466 64491618 65293235 65230276 66065416 66040467 66379545 66977169 67802273 68405643 68504953 68415557 68885534 69126637 69149274 69564539 70101240 70872790 70830690 71216490 71554904 71768787 72401648 73360809 73564978 73829033 74340677 75081493 75610368 75891338 76005319 76466216 76932459 77810651 78676124 79511215 79886018 79855743 80227949 80118456 80183431 81092134 81689432 82582873 82732569 83417025 83542711 84064657 85056393 85080949 85963414 86466105 87160404 87311291 87487763 87573504 87857703 88625814 89530237 89895831 90790044 91344493 91969396 91954043 92876771 92894227 93171720 93814929 93899434 94262438 94702051 94612119 95505154 96476327 97234736 97191902 97678870 97595214 98006327 98906177 98815706 99309493 99622997 100020617 100885578 101849876 101995517 102736986 103243511 104175075 104719703 105596480 106451749 106712901 107331711 107434555 107878737 108648625 108840661 108838194 109392552 109302248 109614431 110128535 110070895 110681632 110630562 110699254 111535042 112276895 112271163 112471660 112384521 112806675 113269907 114072901 114507749 114638749 114843538 115068519 115525069 115836255 116750562 117722472 118710208 119630245 120454264 121097887 121447752 122186009 122976552 122911150 122805236 123079453 123198562 123326330 123604400 123933776 124181688 124585511 124696432 125026031 125030931 125769427 126411996 127080986 127778920 128088873 128201687 129046896 129274947 129690618 130508181 130576733 130635404 131475067 132382878 132986795 133824061 134465501 135254949 136197741 136112161 136168363 136189276 136842080 137398018 137995763 138276145 138166831 139037980 139391372 140267052 140631494 140716287 140682371 141275815 141502613 141712423 142057546 142194189 142461574 142894334 143436915 143740395 143716800 144181248 144230314 144691334 145166690 145921695 146664434 147424012 147483612 147746928 148670730 148710797 149300743 149211328 149492887 149777208 150035741 150608258 150511580 150516493 151026076 151595116 152274354 152647257 152804019 153650435 153986677 154390758 154797727 155725379 156487980 157078954 157314658 157229247 157345179 158146893 158594381 159146174 159204981 159277963 160099962 160366486 160442143 161025716 161653323 162163237 163100963 163102226 163624963 164119995 164012433 164863972 165817626 165823243 166730033 167646189 167912728 167896041 168075162 168829797 169724192 169897933 169844309 169975053 170966104 171063145 171282316 171478657 172464135 172354037 172353000 172735711 173206113 173120121 173123722 173472677 174160744 174663384 174912391 175469322 175851727 176021651 176839330 177094846 177423578 177985298 177886613 178015761 178847503 178862464 179599656 180061972 179969072 180775232 181671135 182453831 183434736 183987903 183932094 183914606 184304072 185054152 185466970 185783706 186161925 186672574 186702367 186888756 186806294 186847870 187735185 188537635 188941642 188992640 189670840 190302623 190250467 191168984 192138786 193102199 193041891
364213441
7000
493 74412963
748 1000000000
571 1000000000
251 80940625
853 1000000000
30 489990485
352 261205481
490 440550955
246 1000000000
574 46706210
753 1000000000
814 324958609
721 48630967
411 168151164
432 195428818
495 11492933
888 1000000000
28 60839959
453 26479390
158 440669577
37 125025571
448 382357611
202 63664042
298 250127083
839 94777170
348 345392480
653 1000000000
595 202163594
407 185503508
666 1000000000
141 20203408
637 1000000000
16 119741389
801 23366374
662 6042422
849 326159285
805 93335701
73 20387740
893 1000000000
298 956100488
33 327470939
307 105806136
461 212441828
600 1000000000
645 102386591
321 206715140
786 135547142
47 13002362
215 257258727
157 46026830
220 175005279
156 153742389
186 36072687
515 190908807
388 266144948
318 259294560
150 158310782
761 396715124
132 108221169
673 280262675
143 296350031
217 370102608
330 620552792
305 372245733
762 80141932
274 1000000000
82 558003242
27 518718869
794 99844541
708 166882848
642 193865612
830 434646982
267 219101581
683 32498500
424 63415458
638 1230364
641 104475452
168 148652195
271 1000000000
891 43103758
217 73521487
50 62634974
3 167047124
222 1000000000
786 134668489
329 199392589
525 16521862
225 759924899
856 1000000000
286 33556058
84 193517779
307 72580344
640 232871016
820 690591007
284 706497616
449 1000000000
696 165544882
879 1000000000
201 284549866
365 1000000000
618 141355662
203 5064224
508 34736694
457 393319275
425 45637162
448 32109397
643 181990123
115 20009925
442 127532703
803 129823462
108 3068220
643 473897664
547 10154159
23 209647353
663 330017494
439 4049640
370 567385556
652 121359160
406 6197891
801 152543836
546 318124776
83 72506274
871 124996426
136 89827660
812 191772542
262 19836654
701 87994878
729 917955517
543 16188962
107 94324299
776 14760534
78 679900645
86 150726355
106 131485708
749 96207224
277 5556143
184 589963191
1 119679707
175 274847824
421 32649709
342 248818814
118 351327224
74 152365324
727 1713330
350 198208062
896 213741630
542 72557958
561 220388880
91 50143504
567 58619883
768 61716422
329 3544900
245 325895805
791 177770840
58 1000000000
834 11824051
432 249548638
113 32403229
626 222301436
9 56619846
433 260080644
416 607477696
304 263737054
104 103907868
891 1000000000
120 331612617
146 124349605
513 904972226
766 1000000000
470 752666254
226 7461068
535 1000000000
646 15676753
9 253551115
287 332687152
146 145848245
576 54065688
461 295914530
549 169068084
475 93032283
655 180458575
350 179613604
181 242787538
621 797280855
875 36880484
620 1000000000
294 24917315
460 164484043
488 114955435
500 179441678
264 1000000000
96 531353919
167 63655956
817 169661963
67 140114752
450 57561728
719 402590809
655 317736997
383 1000000000
5 129580046
468 202555293
667 271760470
533 65844309
577 127830008
55 40225147
115 260864636
600 506327308
362 1000000000
798 359111439
189 198741703
781 60160537
21 136678258
203 29328241
417 73261557
606 526190568
485 596677
157 303200274
609 215800087
213 18086782
310 225391969
29 0
603 43361410
93 84707753
580 300308879
853 176492797
726 148912839
374 94083472
276 54246061
855 101198472
446 143400153
109 47831211
429 15095122
95 49250163
460 173388917
617 1002774
339 32090350
175 97291061
686 30708886
718 911997424
498 622125137
597 1000000000
514 54650968
876 352110745
575 90497450
108 441310511
667 142842312
347 242305225
29 71933893
104 97833095
138 135834779
872 164796702
144 165686004
477 156886828
386 1000000000
10 479760923
336 206667151
168 2049762
351 112977555
26 562510509
362 0
232 112917756
321 311190809
638 553771534
640 1000000000
685 1000000000
748 128633274
492 394683681
109 1000000000
883 299748216
837 5296701
655 121457059
854 195254294
819 1000000000
411 167033036
671 475076517
125 99993566
628 26207155
466 1000000000
629 305180534
868 137545902
274 700155
403 74969073
832 140744237
757 3823587
41 182978887
496 144427338
216 1000000000
856 121038994
322 175115168
67 191024547
317 71246685
731 737240507
440 25795173
604 25691341
59 301221514
248 355396260
735 15561649
721 81213176
407 163906992
566 169899910
224 285106988
656 18009607
684 78346934
694 51971383
409 152352422
352 51680806
115 129272602
410 19551082
132 327392965
545 515522352
330 676106731
128 253478137
740 198480312
156 236177855
459 314790562
223 358074434
410 58412579
863 53736499
253 55405126
324 1000000000
852 1000000000
348 277496572
424 392968056
505 143014869
160 161518766
151 18054147
77 876290039
596 835176536
334 17040384
386 1000000000
683 30407571
36 252095919
852 5069272
683 197208286
54 69704614
778 179121613
100 26130365
845 363337873
750 169815897
240 95322779
893 67202026
128 49395622
675 13976436
632 1000000000
287 684172999
820 33349421
722 208569573
889 87055882
270 52587770
754 795270008
370 327727816
179 114646440
107 260270462
661 9368099
708 1000000000
659 706922147
241 2340668
733 1000000000
622 192154817
452 143901418
224 547719088
427 286671975
682 49489633
170 119741278
384 57335437
606 34278915
99 97206254
861 101431793
694 185777537
114 175408165
649 104780630
266 53128946
313 6490506
631 348958154
381 227969420
184 231834162
233 516228254
745 35814410
818 338646522
519 39981314
190 7138163
369 341097121
208 1000000000
319 72366822
209 73589825
594 94744255
591 11103482
233 210260206
365 10435869
440 734548317
171 227933467
88 80725245
238 33428980
168 63272730
893 9818857
660 107124866
137 650994309
204 22421204
812 1000000000
649 1000000000
812 466160412
362 378985769
745 266784459
100 239237194
681 1000000000
410 202721
582 193190056
44 262845742
187 424815342
846 10264175
221 1000000000
621 168563796
539 4896238
128 1000000000
333 526824567
787 56285724
155 65847469
663 760414
858 295299954
15 20538101
885 1000000000
223 81236477
781 3348746
456 128691634
176 120630144
492 875039173
253 160859409
694 1000000000
165 367091079
815 92691628
230 44860768
769 113606358
763 232512131
647 55713763
592 343426167
774 618969675
69 878250837
748 18728299
203 5438043
623 76711031
190 154077028
51 570639194
252 175858138
415 230817077
859 159799619
755 852143014
658 267872129
115 471892367
670 185293904
824 1000000000
402 52808090
133 29170730
550 329431933
134 40967924
658 88371241
279 129765647
143 1000000000
89 18931806
872 9792413
815 110567573
265 95782228
666 393547161
419 189637814
801 1000000000
393 218835556
128 50964294
235 1000000000
23 133349139
782 721614943
731 33090052
417 632395161
87 163113851
96 55185571
700 3013637
380 1000000000
552 3880574
123 52158826
85 445146
740 337439304
295 217064471
712 27609950
116 302641157
601 194726177
290 179863454
50 204405040
165 1000000000
695 274248304
47 56740378
821 19394498
438 170826873
803 31453914
1 28831204
266 173072722
577 412802904
384 1000000000
221 67207405
823 46829694
693 67080945
434 1000000000
385 41043224
618 146131106
270 237261077
898 1000000000
863 683750735
298 211067085
513 1000000000
819 282399309
526 132008446
408 527934
860 87025026
437 112196492
399 323427315
282 35792412
837 30361329
392 36187270
516 34540938
530 341967002
227 86664240
533 1604364
487 357462891
739 13206095
103 85288730
346 235893641
391 75002933
758 30849420
60 18513503
58 122330956
864 1000000000
410 83219945
350 258301398
70 89889193
651 291635528
870 229459677
353 1000000000
487 280080760
583 1000000000
689 137614849
117 427740585
558 585527256
564 2809679
708 996780633
555 346729176
482 223362695
718 312883310
597 96418206
358 358728271
531 5757366
678 128325451
103 417944823
358 38327548
206 13969178
279 142678726
146 626347313
264 36775446
582 226258550
709 1000000000
730 83159435
590 3082071
295 977291
416 306279459
256 208339158
566 38481565
149 219029285
281 167966915
107 564317896
664 35338193
397 149440139
107 278806976
519 140274141
530 1000000000
77 142227052
702 159589890
860 1000000000
254 36044386
728 167751487
894 18588577
595 37799397
15 100201927
847 252098834
268 310622898
79 1000000000
521 3790396
799 448527453
435 1000000000
368 4273371
213 46854092
165 44515112
363 76537463
618 1005498
333 139408805
404 36251505
352 316191113
638 1419728
347 157557504
564 51986245
331 37650
231 307969844
6 135446488
154 58674132
427 460375834
321 82083841
631 1000000000
173 331613475
276 277501364
77 650535542
857 253860331
685 1000000000
34 212826836
473 191466158
524 341707300
70 240915513
710 430728720
851 310980793
16 49725867
869 570186437
150 138469649
522 211639345
65 14670556
432 70647194
365 247259890
511 947393591
540 196115737
657 68964921
148 1000000000
588 11448587
424 60017844
312 2175688
601 725950700
867 192021912
785 497175926
23 332233661
694 154447153
36 159312979
752 82244534
484 1000000000
621 9307015
629 102636538
172 392135397
302 256263742
94 1000000000
840 612286449
260 5523513
633 1000000000
39 153425864
272 102455615
899 156077358
618 229618324
398 152492564
373 23244970
38 289249512
748 12782724
654 1000000000
895 439126549
327 2576383
295 512269450
704 112897069
11 1000000000
381 27934873
223 133661122
294 760604058
532 532620290
760 4958247
13 447940002
670 312247515
690 525128211
169 427484977
87 203702841
43 33826279
341 23385779
186 207852804
635 56482722
274 5272912
142 104810059
89 30080456
209 192162087
493 35506259
688 456733426
14 248258263
543 1000000000
626 335796027
567 119550683
595 255748683
891 105792138
828 51131196
339 1000000000
314 598674497
452 1000000000
204 65279242
653 132665924
6 1000000000
278 235690786
296 187234462
620 684273286
475 142200474
742 2136865
130 184618099
416 60618176
513 24793891
807 25232894
553 44981652
446 83480992
653 18084079
269 1000000000
833 451967360
876 2805625
62 1000000000
868 257073581
403 233430728
512 27201757
156 16104491
629 36309762
206 299636
797 889666488
276 1000000000
878 48540728
810 800498203
540 10213409
509 74215391
857 57995855
847 106305516
495 36313379
191 73929914
138 6926191
526 322026268
156 58223400
698 261710417
255 62573744
826 110847221
543 259553976
22 253943069
714 965040116
463 1000000000
882 97065846
188 31312676
618 62304035
297 242975972
283 207545855
591 224566548
323 5023462
701 459446182
269 2905605
811 273488757
506 21048489
54 119351335
308 21766311
217 18031056
102 15258678
284 391591667
384 449131524
75 392912655
595 347329998
599 23043650
710 928969880
103 85689373
649 139198451
808 91951720
205 980270771
469 399919686
97 65222985
38 1975723
685 388210251
539 1000000000
93 115741223
709 183756524
478 240946103
339 428335695
523 44842348
149 737486
545 3909077
644 168958468
435 39517279
831 647226988
61 442993521
730 894092062
655 76739914
886 1000000000
482 1000000000
489 123181087
761 156499242
386 29631555
180 31321911
742 219549001
108 133069573
483 1000000000
28 197950081
44 137440186
492 532295814
350 126696821
721 1443101
783 478312179
898 32927234
825 74185704
327 1000000000
332 91811477
41 145184415
31 1000000000
503 2627866
266 502835471
785 70117603
285 46526032
215 38692764
773 8455876
354 272771539
817 296474131
797 663038178
725 294979723
493 444767071
21 62294866
144 1000000000
882 402208666
400 392177533
136 305587989
845 485866703
561 26850553
561 298672082
795 86171795
182 185480678
449 12308980
360 467893498
739 351419197
213 6576207
758 435080278
587 210248658
173 393732004
421 983848393
121 1000000000
256 542069858
824 389497604
19 253392610
520 17644999
382 92313502
705 385038965
882 437381812
249 184836470
553 1000000000
110 13282450
829 15193343
220 1000000000
866 187731471
405 110076165
639 82988339
59 200374096
200 173249515
25 685256760
89 330467936
476 279480345
451 23111934
59 134511252
393 849686463
514 322314760
615 1000000000
501 482241502
602 399615589
9 113857463
553 508183569
257 255925373
376 151657922
890 21965856
507 14235128
206 4601551
767 416569334
131 210485833
15 4674706
81 379548022
560 185510776
134 103549610
721 151018107
412 1000000000
678 235796993
794 873776468
243 66390490
673 265515152
149 185603641
736 1000000000
247 508902110
631 291904368
289 722309290
119 287298635
484 660972512
570 223561977
503 46430649
763 823161961
570 627190012
631 25185216
114 282244313
84 1000000000
638 1000000000
797 556730501
414 10784036
386 137194434
119 197612352
796 1000000000
352 1000000000
542 66088502
845 81263121
316 116522881
282 174945985
539 289832860
328 280062565
354 119244693
790 669275461
597 150290009
209 5182744
833 67861144
579 94674065
93 425069915
402 264603109
729 220147779
458 40853798
249 169924365
817 25443596
874 49053307
77 142504840
539 3907242
278 64677876
81 493243697
470 154603102
335 114511982
459 355285383
545 386813370
792 473124898
103 619071043
86 231432392
342 57931026
224 260402499
405 499855409
598 80924898
356 189048789
217 117534822
180 44612892
583 255460569
240 20548431
38 958829566
424 66521881
482 160904373
825 71423450
146 273775889
314 158398094
762 1000000000
291 217877101
646 202305831
844 225715981
283 181201834
522 80949153
188 40527147
440 217034646
481 867854113
755 18434075
387 2549148
754 1321840
77 11030482
697 325152862
783 24946234
208 383900000
1 3340273
300 140740992
164 2583045
108 176636994
431 149542364
192 100160414
839 104158842
857 26732476
183 50471610
866 11237240
15 1000000000
327 312292067
775 506237752
641 1000000000
528 625687998
270 138450579
529 72750544
561 229064772
202 92561380
643 169361061
468 1000000000
598 107963911
294 43003868
813 426977750
180 399096279
845 120822851
607 249444880
264 72422542
330 18642854
684 36434145
633 875783282
1 16147312
761 57480403
10 339665378
856 207807397
879 64038794
465 1000000000
800 6287574
877 276679489
142 101203844
222 27664770
19 39353425
139 179913711
726 78826970
440 382089463
348 310145701
406 455433675
443 22800243
448 1000000000
174 1000000000
671 604759970
702 36418146
421 123101697
54 1000000000
772 1000000000
478 106978903
472 20044801
402 417768375
27 1000000000
687 113763425
799 448168138
184 10574844
183 12505784
706 261708942
820 420495454
71 163409129
177 688285050
361 527399039
314 50202022
92 311972104
863 145106098
470 45298486
165 63483434
865 1000000000
195 569127469
509 421106702
798 285340795
892 10233815
777 999283220
536 461557351
880 55264926
608 291994696
259 40195555
701 19645293
187 1000000000
322 501442168
243 56349369
223 164373227
567 187694564
704 1000000000
268 1000000000
822 228397471
16 264557960
780 101877945
90 698022856
242 136177314
75 14219049
801 1000000000
1 223367045
484 640580282
355 17469889
360 113336454
798 478532545
419 64259709
825 1000000000
555 88079820
656 325204816
167 981251262
843 203221922
352 125441769
703 1000000000
313 210991360
735 205932591
490 247556799
287 250575457
280 1000000000
44 388360450
389 14874300
249 7299559
868 123005339
274 822582576
378 23437150
556 91525927
181 78921288
446 45531390
372 604026
868 90306085
803 47047243
867 926565094
651 93171952
569 507144134
123 515689006
109 384735176
579 301807149
784 454659872
556 135236413
236 34066799
189 57644208
584 847983
418 279533683
156 18630164
500 486622718
553 63168514
518 50924937
846 332032329
188 299581430
688 13600870
6 556687015
149 383887466
701 10782185
191 196905046
796 1000000000
678 50083529
324 264152416
196 1000000000
564 27277821
243 83615512
264 118212349
562 267196097
372 699294784
58 13689392
277 157218689
786 121299985
822 225160407
62 154524783
243 31693902
718 107402119
305 3607036
243 603453898
563 555832082
120 264517416
701 64044682
642 283044015
532 210537859
756 1000000000
579 75979222
674 1000000000
174 41701778
208 219742535
745 1000000000
23 528372101
533 81356560
558 915136322
237 1000000000
473 113544328
322 132096826
401 98233289
442 260802409
424 56243727
36 410814567
857 127301289
641 9430274
461 20947283
667 35886749
58 220161928
609 40893541
199 536220652
295 38326297
173 19541408
42 130695690
531 614846999
365 79447824
489 132919306
788 131885200
491 16170092
131 90354857
550 192556091
167 192443565
617 179993420
420 52291501
108 1000000000
612 82580461
32 131878705
181 79406017
396 1000000000
394 41624718
868 1000000000
7 160201605
113 417605914
25 78359585
138 299236963
115 46637263
231 10467693
486 109079509
593 644738314
28 293267351
718 12732231
711 332435445
161 29701772
83 271490800
3 162280001
282 378604403
634 11047346
58 79072041
429 147659141
419 766575536
36 89295404
255 136830986
740 326881114
252 667896360
380 150449097
305 70810730
21 71787254
135 381147137
185 5815289
161 1000000000
814 58554290
535 1000000000
12 11164413
9 8823004
189 1000000000
544 107483184
855 1000000000
83 5479607
845 191878295
395 688771386
348 200910997
642 142467781
707 355471570
234 94162501
358 106237764
171 30245202
821 38255376
351 10238697
417 152454953
404 280946110
241 535182390
561 742491292
538 27625029
831 168918766
854 218317715
441 200379440
724 1000000000
279 225180800
269 423937800
690 26475170
203 181362415
421 227234117
645 223005820
240 324013486
759 799424998
379 88211448
717 109536018
863 574552467
528 1000000000
307 630460
60 177395540
891 101911507
415 186814959
168 5931122
11 536519360
749 115610176
119 65657625
106 309038122
224 1000000000
348 21416929
297 166585295
678 47416212
562 101320943
824 1000000000
43 75873338
767 151739031
621 99773735
810 122713365
483 293198576
601 83377491
145 47711088
869 292288821
468 293039482
120 21824985
15 624165708
504 228657257
418 1000000000
661 98721305
762 423313351
722 1000000000
202 66230507
831 2649519
250 48489283
464 21613552
151 3725850
834 1000000000
495 242128522
900 41341026
649 336826138
62 63976541
474 102777967
445 395022963
560 212754895
868 88716649
882 85067556
271 160130646
608 381537336
595 72941248
311 189771070
647 153015417
230 22763301
843 462246800
890 128642977
635 293206632
405 413576686
188 591848529
641 335194864
77 117256063
145 216717194
719 942630560
898 5507337
557 7154162
631 68733487
351 276829956
788 630373749
241 72065162
662 388347609
524 236566877
576 385545363
399 86741220
898 97369638
662 17048976
664 204830966
670 6710681
895 912845120
890 279712862
698 5848158
738 20743554
50 278382556
771 180189870
397 4903796
183 496650700
397 267907266
121 270857248
274 135787384
498 86113326
471 529568841
28 182065343
852 12894690
98 1000000000
637 85138185
105 323326744
814 408397039
147 33635190
368 295264321
694 1000000000
503 24694247
562 148036277
761 15000408
198 407955046
876 842811771
802 156879784
71 129480815
646 221237070
811 1000000000
139 200095749
138 33284174
707 1000000000
891 79299139
277 149320142
479 89542195
254 148043853
408 44546307
732 375980306
177 119129951
894 133047292
414 124935114
413 4303341
356 231677383
664 94624131
578 226863949
155 32568468
880 75819249
802 379265047
815 444741895
298 1000000000
330 125235255
342 32931995
881 318238267
39 360941337
272 144769230
51 26419978
448 73061880
308 40489399
601 10286038
74 3138377
573 210328482
75 226626683
834 573586207
425 175252771
579 34860246
844 240617130
796 226607795
522 306721614
586 37931869
125 200910928
280 22436106
224 59136825
190 102166169
160 646727822
481 190232144
688 171968992
308 1000000000
832 644103159
27 1000000000
504 48701691
811 91023878
889 207131993
395 86375193
298 171185719
583 67516310
863 147539160
876 51342044
617 1000000000
885 1000000000
859 91375581
578 132004083
818 851447332
615 1000000000
96 736092182
61 288007219
559 259403336
843 1000000000
262 236602726
322 819427
726 141535665
112 127406474
802 196091398
431 150875661
802 1000000000
775 185963603
267 461282233
698 183632311
623 6429674
838 1000000000
801 1000000000
527 33073310
58 4141816
255 121477193
660 565092549
744 161805397
298 40902506
582 227198686
520 208139861
315 58541760
591 529497666
377 428530290
514 23013953
319 228639665
753 63036174
806 125590539
97 158409795
740 78667654
393 1000000000
80 815205932
89 1000000000
75 12060530
282 67281820
619 2887199
271 468440178
403 237756401
768 599164799
51 380803981
493 121611603
264 1000000000
351 421086301
37 847537848
229 11649494
454 23975072
708 1000000000
116 387829970
555 163787110
882 1000000000
818 97188148
620 210690209
765 519367
758 309730235
165 90492544
629 38472653
897 141398932
680 117583549
273 89834875
420 957145414
774 235520215
320 86004931
163 288122347
584 1000000000
508 50742574
888 763975784
622 28478630
97 81641382
596 110355140
630 1000000000
130 1000000000
563 5718846
276 1000000000
69 197095792
855 109402933
131 1000000000
218 5533784
141 336463213
430 1000000000
436 75036385
677 1000000000
267 125214181
2 1547574
466 125821040
558 25334762
606 380497734
407 73890153
574 79296732
744 2197679
762 87199410
489 1000000000
78 202219669
679 4786503
879 384843629
629 63324164
224 52297612
531 41274887
602 575243734
321 169297217
495 1000000000
340 82993716
433 36861672
740 494698259
652 296627333
755 166478
70 325553076
355 255335977
229 1000000000
671 103939801
489 383923517
32 32490160
736 184233819
252 86360795
688 3433892
813 223425922
21 111542815
879 775111530
181 1000000000
400 584197614
422 238874684
286 624235246
127 106282654
525 1000000000
481 95385940
535 1000000000
450 394022775
206 101603929
269 110158920
254 49762117
47 2673318
473 207755285
442 1000000000
513 50432891
125 221899465
693 24686026
760 120554576
326 781237196
208 218484503
195 162381122
656 270198828
520 20418026
56 23966129
333 5705457
133 1000000000
851 547051171
890 226483180
613 24270983
387 304872516
844 336125218
488 1000000000
378 61947879
226 10638887
821 476940439
688 23848315
93 1000000000
79 92411993
572 1000000000
206 209059286
884 1000000000
785 84930769
61 44265399
88 456308379
369 172562499
792 692559801
718 1000000000
500 73710659
619 235825761
672 1000000000
849 160639857
165 327214394
735 150679573
266 229750090
781 33611019
755 158247428
479 211872469
305 686069577
630 2570847
47 8295421
609 108295112
253 401116203
76 7262928
368 36919020
228 659170142
423 380113722
556 248199638
114 1640205
740 95055341
593 335851628
553 264965584
601 218209303
466 7544122
701 30287868
739 17900995
830 356840163
81 333945165
526 169218456
599 46188056
599 325241284
841 56791317
745 18430543
148 56527794
686 84769658
654 70664049
256 1000000000
178 1000000000
315 14296238
33 671966796
613 236720584
157 196946231
216 22185333
501 338769373
895 64262329
257 127300591
87 729799589
738 43319180
199 191651537
339 87932818
423 33203485
868 280970337
148 88596600
450 1000000000
596 3167866
884 588564389
801 211489080
638 337834725
27 95224808
629 1000000000
453 153433432
652 126927607
807 260500893
407 225679041
253 243802253
126 7135296
180 377741491
14 164185247
619 162330076
658 128997221
98 340686906
347 774829665
866 4520996
612 50823393
26 243451310
317 303130806
818 129539131
422 827760969
6 228383700
708 105627965
891 223791457
186 75150186
240 1000000000
896 45203865
814 92218549
695 1000000000
512 343994196
790 23401238
318 1000000000
613 45506205
344 112877223
221 131319095
235 41592055
712 366899689
842 100474003
733 368333589
305 26583190
429 181925931
605 63737278
710 375221784
505 133165887
343 4863193
9 140821629
653 55388266
574 648314483
194 102907116
619 19002496
28 383406717
608 29707085
311 399078187
702 515357614
482 17517223
648 136767203
117 25854579
190 439154546
324 514856737
368 294832370
36 709464361
131 229124189
424 30709118
718 860375003
820 1000000000
306 1000000000
860 801568283
53 265016
781 142373489
653 15115845
42 884218171
530 18701480
32 24353728
482 30840329
682 1000000000
859 689819142
56 140459322
145 50658470
654 4965189
166 256224882
749 180347210
492 62380085
400 296288730
738 420079162
324 403498501
445 1000000000
299 1000000000
256 182381579
731 24157864
331 240664356
20 200051328
239 23445779
44 8342643
722 93188383
849 110893358
578 1802833
579 158920035
899 24693114
544 102386913
208 39579242
70 132179825
617 1000000000
636 219421098
502 55384151
11 93284148
496 301974249
514 35992753
318 734228647
705 332855509
572 6919796
596 950939018
743 36664018
108 142690102
154 4236690
240 204482045
89 113660411
820 641618436
500 11170527
229 533846845
832 323053036
406 25176786
620 4169862
384 444601647
529 488580353
145 1000000000
798 89584940
711 267122151
483 4714728
369 55023035
24 302411049
472 357443508
442 416487037
843 110993591
268 86676244
110 159882437
862 293762516
766 149721354
321 174469048
669 218896472
576 24260679
166 144653766
271 124157662
330 54290280
415 181560832
859 741682351
355 32974413
292 434674669
275 64678153
1 461794042
824 81742365
579 142569839
36 6248635
165 129814503
666 187448515
323 3484372
295 40183671
750 113693603
577 1312525
457 3183757
791 1000000000
692 806087566
578 155887064
276 42765884
592 1000000000
424 1000000000
167 1000000000
292 136604020
695 761352304
140 1000000000
674 41759351
325 658510936
830 155728222
622 388384327
415 231643683
72 70538967
67 247701598
378 11352661
396 497284549
424 172486535
65 243933321
678 289515760
379 432964779
261 149329666
105 46320283
896 284407837
543 764116684
555 279430077
105 1000000000
511 182291132
532 289830746
7 23347397
27 123220270
791 26794580
827 187598843
84 3869691
299 111009132
897 1000000000
323 971669709
882 206282604
863 150377142
3 121191176
832 2931602
613 155218307
181 136656481
635 541606181
526 1000000000
446 265648810
504 97175122
432 1000000000
661 55947596
664 224950746
92 498160177
607 195422631
106 153508683
819 142401128
33 153048471
67 193957027
500 350906631
103 851048252
404 30612501
872 703571306
568 316413656
821 1004776
304 416019076
846 30390647
80 1000000000
83 17789960
357 371956847
545 914882
674 45462840
860 245563164
255 77879799
854 294974692
773 62951944
777 236946172
803 3054127
376 74176588
765 35824055
672 97008641
492 402642946
199 157179834
183 73760612
415 21354540
194 695133946
520 420016148
26 95340469
192 119957034
553 31370687
562 55180524
806 247438923
511 92195763
590 218581143
468 583513755
507 37921184
94 72782079
152 405526197
33 438372658
393 19029997
351 109371040
15 103216362
298 186331466
661 1000000000
705 650744953
28 268934712
497 467386076
474 185663951
373 90482080
57 125427898
521 69924959
389 174033744
785 645093653
536 1000000000
310 104365021
304 26021316
887 72951243
268 185603481
525 101480103
257 587537047
442 1000000000
78 37414696
108 294921154
351 37832638
215 140572800
724 1000000000
9 157655451
630 266435160
656 185975696
772 221640176
292 171118329
867 166389185
67 188158931
62 118190542
703 118772088
897 152736203
803 47923123
232 5720461
280 1000000000
680 38132566
21 208822687
716 70654191
54 251023748
508 29733305
435 52273927
501 394376783
177 122664777
213 459703724
775 113853748
795 32450676
609 265168798
584 24738691
24 879538647
518 1000000000
811 100304915
552 527572404
342 1000000000
475 310359895
166 10111815
74 25387331
106 185159551
861 210344930
738 169898807
136 64668934
147 115062690
136 114028116
532 42841027
24 83765761
813 540528348
352 81287139
123 574982292
765 1000000000
604 8808251
870 155729671
899 167822794
859 1000000000
297 45474202
357 3730987
492 252313101
759 28026359
543 1000000000
717 23405890
898 93206828
648 128322826
386 1000000000
802 220788057
714 152671315
430 117736948
282 110892710
609 19482872
731 41709824
445 109798597
304 184533673
661 264345534
685 98521947
569 276762727
59 440151609
22 196790021
105 267796804
735 603360872
279 68721496
101 284085144
805 195270279
86 22826767
296 12201539
52 367336109
407 56173799
167 26557880
895 1913603
341 4738141
187 55063138
260 1000000000
155 71871989
287 394520054
299 474316716
11 79190423
244 23714015
743 215136422
133 487112749
131 356247326
70 186439552
255 14703800
680 45265805
256 361166134
438 380362062
761 1000000000
324 145938496
743 36723454
267 377600480
476 146514012
165 1000000000
159 171001181
453 203858352
185 654612163
324 203470377
616 715302499
644 147661957
103 532080310
588 609762673
502 1000000000
393 349588362
269 455480392
749 85910917
669 466042850
102 1000000000
730 25034381
148 136393994
158 20791118
298 176771765
211 200806265
620 1000000000
496 1000000000
194 19324909
714 251520540
685 147831215
716 120429657
848 50169440
854 153974842
363 4631007
288 348029967
322 1000000000
411 202496916
22 557201683
266 283845613
22 577737137
813 131279000
891 95019106
741 180260220
468 201462948
185 157174420
753 1000000000
485 1000000000
842 329432331
82 1000000000
396 274563143
499 891868515
374 1000000000
620 234581451
629 129165082
350 195370549
747 14472831
867 434868102
718 370190
574 259896314
182 195855906
256 180770747
609 265412956
519 493405272
729 43754608
886 241402509
318 11081151
377 16674211
358 36880103
381 21614912
735 25066305
637 232600175
744 1000000000
714 890095361
130 10229750
214 141290423
640 126956141
699 320479264
254 133344675
805 132389946
80 186058005
774 89023905
691 418863953
72 1000000000
842 212498234
2 1000000000
754 57335077
757 200668901
581 550935211
256 88735187
69 100311705
739 205693361
78 226038419
758 106142222
310 1000000000
326 401848031
399 60613605
526 375424778
604 42065056
679 125332585
602 192678405
687 403322898
616 82517532
784 25333346
582 7416025
362 157844343
749 123885568
888 25469319
603 100280564
686 437080518
595 44884612
28 444785812
106 138427870
134 1000000000
114 15747253
125 446910643
874 1000000000
413 61228425
42 386774813
88 1000000000
355 30509530
508 416780592
280 35568835
832 130837425
565 40418964
833 710550075
95 16678074
481 1000000000
345 63118255
107 123576110
31 174386453
832 551288973
722 1000000000
602 881428582
609 64048440
552 177940797
672 27516569
818 7343819
675 86677554
789 10075934
479 18690788
564 148422705
603 32418320
707 250575657
508 1000000000
375 761546445
245 201489010
559 87278043
166 333297389
751 107375214
279 250271225
527 19298561
781 65405364
288 286723259
215 74494643
586 172285295
601 167944993
227 219202517
820 554609836
385 154372014
131 257400714
83 295736439
522 94524958
185 376010690
194 716083760
432 110367039
766 38866253
627 1000000000
570 52716679
867 243157112
690 331632456
834 1000000000
163 1000000000
70 66948275
640 360231988
666 17214535
342 65725854
131 66977326
336 18960507
308 486269083
386 1000000000
161 101209095
604 23371556
599 568499477
75 100492127
889 539305489
206 410302740
583 350754081
493 269847181
197 623541396
265 290192141
524 394170154
821 564964844
427 984071958
257 223457896
563 203694209
561 141708919
666 119131805
38 376113778
434 51633702
764 171792214
711 1000000000
721 115362777
227 1000000000
283 122320311
52 65629446
449 1000000000
422 4056593
852 59238977
243 93232749
890 39794506
213 105874105
817 669212988
288 601875
121 1000000000
74 87469981
297 307498777
597 268690081
393 1000000000
676 346148920
233 69357892
588 121516337
310 27731974
735 1000000000
818 94886714
816 12264242
480 220135940
416 927931369
657 180176696
449 58128854
699 170754875
498 1000000000
517 5084016
207 58655215
412 93970489
769 279165230
115 409633164
827 584528002
774 8609930
313 88533436
321 113963517
808 293657818
713 332009658
719 1000000000
597 111677362
550 65680280
722 122862410
649 169864602
398 154324083
793 76144336
43 151497681
629 332034996
309 124045536
26 372558773
26 101196799
327 78063746
768 215652351
708 487999638
315 34028460
797 10994224
209 27118085
199 1000000000
512 1000000000
129 315155379
875 72512803
547 454648100
59 100934733
170 213541945
263 13453200
173 706852057
139 28189923
384 311572685
151 654468718
528 83950043
676 60609803
112 104820268
369 89093648
348 150154237
846 406749915
53 220497112
252 179906180
894 1000000000
762 102147677
355 1710085
573 20702091
680 290714035
159 118016312
102 3851297
470 1000000000
636 402501262
741 484379075
139 9139609
493 198710673
29 148432663
601 249045568
556 424678488
689 292138361
436 110764563
10 12794616
511 126723947
802 521571189
91 56903206
160 98381865
252 36460090
313 84423965
64 83685955
171 3259058
149 52779528
713 1000000000
127 1000000000
615 29346394
460 293614270
450 50019165
6 275990416
141 6175977
264 970030
892 160070528
163 168327044
428 443368158
621 146777882
100 145881764
393 1000000000
816 105085674
376 122826150
345 1000000000
528 1000000000
174 1000000000
700 23274815
835 42354284
232 25091370
20 267676018
725 551838587
362 260432329
870 17160023
792 61519405
779 145140158
311 25844851
173 38201334
662 46181835
35 203873464
777 259510964
149 244504417
20 12536358
279 80247774
56 49420488
602 318542958
544 180499094
269 151687860
500 120268981
817 141834315
685 237039855
277 90937733
14 180606248
769 53856954
399 216140805
517 4685564
337 10039664
678 74304465
338 214507196
155 43308429
429 51389147
548 49154016
871 134359819
646 1000000000
502 130449297
212 94840225
525 46103317
638 88468446
625 452779706
321 136279439
788 114303356
828 15995149
417 394430340
771 133767893
117 296618690
727 104435443
58 141982157
211 205092636
707 5511741
511 190991002
848 361586015
519 291056017
386 28989090
640 606093786
188 733271979
605 69324144
214 77520384
451 1000000000
212 62595100
316 160587450
91 169156560
662 14035486
703 7812879
841 85456874
498 162211885
771 364496795
622 140052200
782 207385825
286 44148267
154 144751491
266 345026067
285 24068604
723 202406884
141 208136958
460 81210039
841 201285666
550 639922993
518 19271922
727 247046903
683 266131166
873 542701
104 217068636
640 275282006
806 1000000000
14 77767258
751 33603699
785 359169155
845 0
893 21080852
56 324309484
828 48160998
419 1000000000
60 20316503
526 21995404
888 71551176
141 107566896
341 96945728
597 63682497
542 154412982
125 93311142
143 576574757
425 1000000000
800 98684931
202 97599322
110 236165498
99 1000000000
872 782004805
516 51397519
243 1000000000
361 79557692
353 1000000000
587 328431538
564 200059553
781 41577273
820 190968781
508 346147172
591 137511994
199 98926692
339 90234644
450 36506847
3 9718386
753 84982056
104 20943834
437 109163444
37 819252684
541 253388090
426 314511308
249 162369105
108 150860903
302 131195537
366 369374885
259 3930568
664 176562552
396 194511632
182 1000000000
682 1000000000
41 1000000000
272 279233860
264 12558713
426 209369304
855 546432746
517 48976161
759 38104938
80 108354757
879 124132429
183 512811718
375 38056684
262 115582567
344 13878920
190 1000000000
153 497952847
666 3964734
38 117180070
275 464954392
436 117568106
99 26300439
30 1000000000
236 4254359
296 49907710
2 511418051
3 218546811
195 763166418
529 109551640
869 2728398
260 50338916
164 31619306
824 6058332
138 55873335
532 1000000000
453 308160656
324 263273189
560 1000000000
832 531241918
408 116155255
609 151304558
8 93612424
462 41226528
876 330767625
591 437954112
761 543801115
677 422875297
897 3513172
183 211708865
454 261393700
473 34552452
504 268620595
216 30639505
534 152204120
615 120607652
720 59123433
102 936379
606 185193393
457 54749638
601 225445650
65 24312846
8 141507675
389 1000000000
15 73680801
470 1000000000
55 39195889
299 29825392
587 1000000000
236 206808734
527 514808726
829 1000000000
19 343471451
279 220071760
424 34059378
33 8375198
757 52756181
287 384763303
411 350083737
290 247203882
77 314592344
209 190005261
535 19336509
660 861278530
517 164030729
780 51643406
96 824464914
891 220720585
447 1000000000
616 55995691
654 20796315
640 212399586
354 247367706
317 167055878
138 1000000000
642 152216367
98 219013154
440 373589000
815 53389226
25 12253520
412 39730439
19 541401880
561 406479204
298 83713567
739 412609120
729 2240310
641 1000000000
132 653079803
455 93673724
251 79107519
473 366064357
731 110117053
768 9783504
510 1000000000
555 289135251
399 242207359
603 2213104
815 319125115
850 99042467
748 1000000000
850 179698278
53 96149292
811 123283835
307 345185155
347 1000000000
97 30375135
176 499784785
571 361798134
38 67008404
665 1000000000
707 732630864
320 48374244
549 1000000000
215 405237482
367 33082264
39 61158149
766 483949217
562 68744055
85 18675603
382 451896137
248 1000000000
147 17882806
123 99849927
859 163459649
631 211502515
224 679442820
619 40955086
894 125343314
44 1000000000
203 173607079
365 17932127
193 251016870
514 31505435
311 266373449
875 190248940
542 171805003
117 42577284
121 229909467
683 227880770
48 32478868
105 761484445
219 55793804
484 116240215
687 128154392
650 575152
187 731432688
354 23896751
759 3978691
93 683166276
740 212300048
857 58738006
305 795444992
757 473578197
783 119240428
458 186282343
156 437040665
399 1000000000
686 108216225
712 431640625
408 3361436
193 148493283
323 56353801
267 79959294
230 189474607
801 948154926
17 541336032
899 220330024
889 1000000000
14 119517543
836 42621329
181 621560942
529 1000000000
728 4804638
621 7198551
344 29032406
810 65048710
704 74913777
519 66695281
688 78885261
568 185166728
49 1000000000
738 29154318
153 51475293
660 362949623
131 211803227
338 157352375
512 309621567
505 1000000000
770 219978362
524 228470724
744 12395325
427 540455821
398 164952718
791 218454877
625 80056637
431 1000000000
504 212286903
815 225996066
352 1000000000
475 59883933
587 106513728
136 20941295
619 418092364
669 82490775
780 60212922
431 5517778
516 330411217
481 87368234
441 48243254
163 191208909
882 353905157
29 1000000000
640 405754
180 295079158
322 313263039
207 133518065
160 1000000000
214 28714796
478 15016361
38 278727837
793 150857659
410 8193374
228 1000000000
574 237488561
440 228140547
251 653544912
376 352038561
72 23444744
728 1000000000
213 20743743
872 430088483
114 40535367
501 180588491
248 89971517
126 386867055
522 523432093
59 1000000000
573 158166096
301 13076911
599 46140014
830 1239493
255 201804927
261 112228962
18 217364275
103 73437394
402 1000000000
114 6271035
350 47184138
773 133094974
486 57124063
489 39819262
511 12352587
729 319240380
828 1000000000
229 362329930
1 183973368
709 649458434
862 357480279
250 189941590
340 131485340
735 18987824
739 52023555
888 922876651
713 28156176
130 1000000000
588 46848430
92 22678824
307 1000000000
102 533973026
131 79441098
485 1000000000
466 73043790
424 328166460
94 72465724
615 177467315
235 64916904
727 13617689
111 904286446
306 287647525
576 122482120
243 274708045
562 850887267
351 179164302
595 323979579
316 338270779
717 106975327
641 148797608
344 163019987
386 275961450
406 457877693
56 243604754
685 422336079
894 99831738
832 151467731
385 301265003
876 1000000000
751 472924179
376 308601744
386 504449131
292 1000000000
162 331340630
816 64323157
193 173933238
37 1000000000
765 13123368
330 122254737
837 111992644
352 32161799
642 366614583
393 640994108
455 168646708
483 22059975
864 591210426
14 19943769
625 5620913
440 175349037
131 129482688
27 289461841
889 448366427
299 16990456
880 100383132
742 1000000000
242 401229771
242 402597393
34 101710662
622 19391861
157 95354891
879 323453012
817 638533861
848 35655061
685 209726093
733 56369755
557 137691274
54 201387786
685 1000000000
860 119145846
422 9210056
770 255700817
28 13221214
644 53714493
197 233159460
163 300774271
87 125742310
342 84110746
349 147356008
649 105667757
584 33093224
709 1000000000
499 200018138
197 78949836
370 36640292
741 337607416
1 755257621
474 226318289
789 241853432
435 712718503
233 113467566
304 76301979
37 36312129
822 713467416
118 108406701
879 67097561
551 1000000000
474 633287531
172 7733233
156 100904578
834 1000000000
67 94562975
200 310385399
354 182286066
718 262916758
469 211038082
5 478784226
285 200135780
627 400940545
301 284801021
343 82103468
877 71299926
866 140690870
214 47121234
778 626313050
147 15019054
690 16239290
516 42237253
130 422675325
570 136542276
603 246403915
120 385446597
472 90163707
798 7063659
838 152215052
396 165541960
603 8914314
223 163939458
413 299569333
654 124981246
132 1000000000
470 558014353
874 30695711
186 964504332
613 117981272
510 350989951
428 428576436
138 38541965
72 124759587
279 251107314
292 169336321
892 23415130
272 330772391
385 128752330
84 546989499
599 5370383
761 113545630
321 221307226
522 79477605
751 485273249
60 37444949
550 39361070
769 199046378
388 41820443
180 53581553
312 199182023
654 256087662
15 195464453
245 13907825
327 311796271
604 35503906
475 648946206
527 85464704
200 40680130
526 21647002
592 26114799
446 83188576
81 262410989
651 98136417
179 495017450
707 11579060
565 149091020
752 106589982
623 60694864
281 130103821
213 304926621
359 101994232
804 695996777
20 103687187
859 519548312
707 226141366
146 125189267
473 1000000000
773 1000000000
860 8940633
253 26055160
91 12268768
497 55870505
370 407319982
270 210245725
230 188535252
771 32500663
362 129577149
848 1000000000
794 4879858
681 88449215
3 6049858
495 1000000000
400 1000000000
529 73304860
637 102226639
780 222172791
606 202983111
618 17356834
704 572990407
889 60642639
475 55418371
805 124664420
581 25982092
96 158496381
732 397710419
80 224763280
507 566003487
481 188439940
354 129122039
373 538458642
866 732330610
326 13745934
670 667434912
115 86548646
631 268673613
201 594323584
831 49312159
211 347725244
596 332366345
357 347707337
385 99709646
683 1000000000
891 698265226
854 365247460
133 622329313
393 60942024
279 282142772
632 68237822
810 1000000000
168 1000000000
665 3610000
776 324208018
868 37864539
361 33730292
751 133982522
809 1000000000
343 191213822
734 201614213
771 58038934
183 118248674
404 1000000000
417 216560575
532 14437928
415 37691326
353 1000000000
421 136075890
843 30617192
72 116860218
189 264767987
794 20066976
250 2089653
58 22676918
629 95755464
853 418575161
875 14758215
53 845305352
466 161944066
453 49586161
358 247076330
505 137557785
689 392318955
858 61310359
213 10734633
343 74705242
649 45881631
656 99846933
870 815712371
698 15711030
670 260747279
4 47877304
16 146631202
766 1000000000
681 918305067
633 1000000000
595 144509641
520 294783466
825 138660659
735 425773065
603 102036653
526 1000000000
222 160720263
802 33846515
853 505111386
274 158578486
4 64004377
431 1000000000
840 6984618
720 40511725
596 244207236
445 853842146
844 826020409
538 241522174
296 1000000000
624 89472273
41 40433396
866 6829951
622 54308933
780 398372879
552 101000988
731 521236787
850 39586772
458 128373253
520 1000000000
421 1000000000
586 275730190
769 91395075
145 136968412
309 28000431
180 12566354
777 199731421
631 482196736
177 802407493
495 622456097
670 67092362
79 498605594
423 345293480
607 88978411
385 1000000000
268 45034976
558 85255153
461 294187480
289 193851858
298 162521085
119 32509191
636 94349857
682 546421223
26 264794519
581 261633136
744 1000000000
848 45941889
242 96815250
376 103264252
525 89253684
856 219850736
736 128681245
308 54322382
756 39677654
780 90888765
47 53604123
261 114483959
579 2267833
251 358460968
356 341594063
464 144201087
476 788498993
346 1000000000
201 143488162
388 1975999
63 9243393
671 242685555
620 112077136
829 124342199
438 134145951
40 203657292
301 11053709
220 39496987
283 151380890
515 218130899
358 142667672
727 337474476
629 34913674
316 76142754
781 395566475
540 181499819
112 57263077
517 1000000000
421 1000000000
699 237274425
725 7229850
692 611959603
450 27437851
230 60051952
239 7554289
500 39698412
520 47602211
323 74814372
766 700070932
82 498082591
652 753418074
397 483682352
658 50178582
844 484015
549 1000000000
348 178596622
272 1565278
72 453879209
171 1000000000
121 114803900
602 10371355
265 189360273
278 33515095
326 376814937
758 39322685
524 107008669
795 7822523
317 61271982
776 413766822
123 321731475
509 201717088
310 38851931
538 187553426
428 657050933
880 192063112
687 212790722
574 831401199
730 254307376
584 173478729
654 227739940
187 35627046
858 1000000000
250 925125797
66 37660139
369 103464428
338 1000000000
825 81130728
359 47393546
313 100025316
344 54128851
125 217548771
365 104643884
450 112475313
367 37324624
899 74437951
665 131421560
548 39697810
167 31193533
329 79649239
754 216544875
243 1000000000
477 427624423
425 93989198
800 26358464
732 198866638
800 486225979
222 1000000000
828 280980864
273 374737287
672 429488536
565 53390940
197 51891250
748 650040638
569 171806383
272 240060807
627 560582014
41 245533287
156 57785465
93 60320617
126 551245097
46 198078251
68 359258436
847 43268509
334 422632544
233 135728713
281 103465248
687 1000000000
272 47755713
57 69972667
463 35201999
816 1000000000
235 129968144
794 10432878
679 6374617
17 155189249
83 362229288
821 100974286
724 86191569
169 194398571
241 109924357
117 577090376
62 18362506
557 377876133
351 22295577
290 114780887
621 1000000000
291 714880
419 1000000000
784 100279349
334 54349695
346 80006689
393 124388515
372 208091804
648 33793219
782 162826253
751 305058168
216 34962635
479 93334735
535 1735050
391 9978716
762 333905102
351 78917053
814 1000000000
324 355187217
186 120619181
817 31220298
14 410228808
26 70175253
710 727346873
112 1000000000
39 812461185
517 129818467
112 8116306
168 1000000000
561 198460371
86 153613394
3 63295323
697 1000000000
577 7479525
832 137939988
239 351147001
364 1000000000
526 83326084
155 1000000000
597 30096803
567 114047328
660 3190879
900 72883331
828 259644350
513 165917721
244 302517927
250 531010249
280 60901283
427 1000000000
192 287497739
401 763217043
353 8654537
707 500247085
46 19884291
797 435125603
768 1000000000
119 217026327
357 54082787
470 279660469
791 116004809
725 159368705
46 86903456
309 400356785
612 233477
461 1000000000
491 187023807
329 65615366
399 540385283
229 275959326
650 140252555
94 131405245
26 38916540
707 43497892
502 152961431
377 1000000000
651 432938761
618 5028854
808 145269197
516 350845895
101 98914818
343 88000722
87 21781190
725 6516700
636 137521554
488 80068483
806 1000000000
728 357599327
881 126170799
543 401224010
496 341908491
455 87548265
827 299377767
87 6870705
870 770504612
664 69640490
298 173584853
101 355002720
882 615527445
394 197498484
842 121974995
331 8686300
335 206284427
269 310812368
152 1000000000
343 768851464
581 526769182
190 115492874
298 1000000000
816 635188
540 88650779
471 426326015
798 24908495
595 90522108
41 416381039
602 999726676
152 842708
162 227811829
711 49084661
802 92223915
898 5269853
231 154960127
234 180282673
220 67540343
218 385595503
757 254296156
746 12587107
239 122112600
495 70150793
528 92312079
796 24289768
23 85116689
77 1000000000
41 64076729
539 42907865
360 1000000000
441 1000000000
707 130767204
375 249514
530 455445632
154 7970886
870 206349988
229 1000000000
482 104558106
516 12172113
342 20628111
843 1000000000
99 526899566
847 216587948
216 48512582
659 118667339
149 55283256
648 51490306
47 108078394
892 171667043
421 62254778
85 98355620
771 73062947
703 120281982
381 123439531
888 151826174
884 104925046
550 17756131
307 62418389
777 26628883
355 2419902
191 4235887
103 817462890
482 308259256
599 54922915
613 127964442
515 1000000000
741 251421265
8 622665827
781 590172675
577 26393836
861 48877566
838 206164089
625 128632938
108 190004868
818 16923379
538 6326470
471 135419875
900 252253310
93 176141234
815 84450180
215 845867760
682 46579588
201 415687398
225 1000000000
131 537036179
900 127838174
622 161536574
552 1000000000
877 292590201
216 236369906
432 84029543
549 274670776
636 65050960
833 229060264
731 43815286
679 20918352
720 153638356
712 97257713
900 256105771
294 365750302
757 265751143
420 381252433
106 314484638
622 7846452
416 37221195
365 163330993
650 418423392
596 327253017
712 32775158
723 4053756
126 106551317
618 164293708
721 8278206
162 1000000000
108 257931710
515 1000000000
307 6594760
291 216260684
595 199458510
80 412885894
255 106002059
109 80807079
679 102496140
647 1000000000
308 133117994
404 208767456
305 1000000000
654 40211761
806 38424074
21 156363495
892 12898178
68 10463727
845 900615956
671 17132927
724 32434453
358 203448502
266 1000000000
70 246621087
877 16247335
597 20299704
544 184279498
238 77007712
3 4501236
726 1000000000
819 13115540
663 348256441
159 377895696
604 145551093
136 708471103
214 30072841
336 1000000000
848 198811825
5 208613801
134 64770640
799 2298954
648 819194920
292 75662113
851 1000000000
410 75964661
30 84425406
488 90194100
670 103361908
183 6874025
37 44598841
854 297230193
609 42152487
737 1000000000
422 38270056
852 84894220
390 444609975
108 226437062
515 1000000000
804 12097023
369 120761984
101 187025545
770 31574447
474 177402714
316 319876410
895 25607478
90 50280281
396 82659320
609 94800380
118 193120808
252 70644620
616 589773694
735 357583238
462 1000000000
426 290334667
797 328378173
478 78954684
843 120235754
194 43315693
91 1000000000
586 309362785
154 298032292
771 76708681
22 82743143
116 1000000000
42 245778751
253 131557875
163 134459111
339 260285809
56 55229404
257 291334796
629 573532049
523 87514868
410 564508588
594 10927659
156 122952512
465 51287972
454 276169012
728 142513668
40 246630449
208 180186722
243 175125042
687 240674174
358 128961978
516 35401993
25 322141557
72 304287782
645 88979003
649 416171791
61 300215374
658 88690804
197 43060264
251 157087616
710 48596849
109 4563927
746 32375585
359 435018260
64 1000000000
457 410738409
329 50580616
792 44101206
179 86555988
695 273164271
221 30282442
694 1000000000
835 787177936
362 25702110
558 65296097
726 284752664
329 544645822
490 409794068
229 57235568
758 355506830
144 671853467
119 219064222
8 187452335
768 204885087
145 1000000000
866 70412524
593 34429352
488 5431665
446 971515168
110 49594040
583 1000000000
812 443237612
145 51308690
639 231112930
743 54649037
494 1000000000
601 142442743
481 912494202
435 846258985
61 350425545
374 908966387
613 479308721
381 184723863
101 1000000000
633 35885041
742 841275768
597 50679864
294 566384947
621 5425561
24 376985027
1 41263463
609 65475159
218 21312755
311 1062077
659 293328199
681 360914761
172 59583939
864 116156654
521 230374208
862 1000000000
847 220479117
186 37713172
642 1539899
13 86402521
680 374782081
81 273927692
163 102357702
729 381210484
534 922390824
825 106567623
18 58385331
210 19414449
386 1000000000
895 36550996
586 26653586
476 53830636
118 35239945
697 11812168
627 599066011
683 1000000000
432 9277557
738 1000000000
581 32251131
92 83184655
391 241156147
475 39541903
197 84890040
770 1000000000
651 21855956
33 88621508
866 1000000000
425 240498392
301 148363759
829 65074438
604 6342746
282 50418379
576 117743177
258 71302122
71 86199078
179 406445314
232 1000000000
665 5882383
124 444313972
38 110351386
137 201157264
20 196055741
190 8521897
619 50066380
671 21785929
5 5170129
565 7891918
756 488976989
335 108713657
847 417191776
538 60221628
843 414579727
804 495532203
799 68949452
735 286979445
395 367437692
87 85670402
43 462511366
666 293074675
900 445075272
330 1000000000
629 802113307
870 459058471
239 102407780
43 281514277
876 14232227
312 1000000000
290 353340200
69 589190580
781 288669249
650 27975868
843 54556724
132 5331832
418 766282867
634 15189798
297 3072659
589 35921694
89 26073948
435 57735382
425 53568182
119 493262749
517 258476025
670 116586850
474 94635479
94 78698458
571 1000000000
754 1000000000
144 304446961
182 236764167
753 145403669
558 316584259
283 727177023
687 34930553
825 316279662
417 68051537
643 1000000000
242 320806710
782 258239625
620 435590930
781 689146129
466 42407877
692 367198239
653 135835512
516 1000000000
664 93461804
236 23713481
747 4870747
8 608667867
734 54365363
861 18100979
326 19263268
678 32716936
386 106681011
799 22166817
650 103370288
688 102667418
43 178864900
666 1000000000
288 358169716
356 134434493
501 55772329
871 684918616
807 493719043
550 329786057
109 1000000000
489 51795102
731 3958280
668 370006353
753 71935973
560 9632670
884 1000000000
428 663064205
320 1000000000
476 28190919
71 271498013
501 1000000000
643 314307392
802 763651735
731 190763128
739 19038178
611 1000000000
241 368576798
244 427586391
667 52805774
1 300667791
529 155786238
275 1000000000
363 5044502
136 409644009
742 261955979
194 1000000000
873 3814018
844 218977305
105 26731412
135 517908401
453 522864124
314 88257974
41 169669742
221 7055403
345 3842392
461 221384871
202 69212490
213 260650903
691 24567745
881 142072079
264 727435672
589 1000000000
726 163386388
310 135238015
300 73343392
707 48426666
802 12364395
553 64892480
781 122669645
558 69958152
147 367701720
300 400681018
67 173083891
175 12087604
666 84928308
478 697777737
70 69168105
253 221910251
354 45622688
152 31293691
443 57939111
247 574547906
819 31890556
699 74539275
688 151777373
856 357139417
286 82825169
324 314859755
736 76849807
301 142837819
170 249843756
210 245979696
240 278587731
112 134377588
39 33341598
537 371152295
81 221706307
712 17960345
261 1000000000
390 15794014
236 56341885
317 190127412
212 309363899
332 1000000000
492 77962110
243 234929474
549 328296638
579 394342900
698 864311275
159 269826376
839 1000000000
583 36028415
684 75473535
504 473262612
506 1000000000
873 74419192
324 179337819
666 814091906
187 122243850
499 159142382
541 43318496
597 56840175
588 762480824
527 77061920
536 800368
482 4586189
491 113723124
685 96200636
227 360890854
236 224653601
852 29787662
395 65290497
544 106517005
575 1000000000
301 30445161
463 50664323
726 65584068
167 430166542
168 1000000000
396 46013827
226 94790981
593 1000000000
556 339313236
346 287762337
658 201080671
216 92625743
641 74884887
214 340924276
792 1000000000
448 127873679
55 38030807
343 675240842
235 528109329
274 8150138
171 66903355
669 316390406
696 156011119
320 7013579
504 518653195
468 208762422
753 390838022
172 1000000000
146 181712292
245 100259326
572 13403713
861 1000000000
650 1000000000
54 66597153
356 17279029
112 101148476
303 21531765
777 5525242
617 558196501
395 14974929
1 408110615
666 20141042
692 128400128
396 86959997
804 232470347
707 1000000000
616 1000000000
735 324870190
128 277278383
62 195016023
205 49558933
446 19367122
738 104339908
574 84519658
291 225423599
159 1000000000
33 1000000000
67 223151851
639 547413
829 88318903
505 1000000000
106 26788201
272 36426856
164 1000000000
55 384699290
218 806373040
710 10470517
752 32530119
541 376684060
131 2716104
285 168375346
666 29575238
373 3153103
309 942501200
46 5648050
829 153280274
723 69161546
585 871298651
740 21186700
357 487951972
273 116342300
269 18720756
99 176700378
418 299125399
189 540538
627 18767158
583 26868828
477 280186793
642 112514901
631 27153440
793 24708773
269 1000000000
844 6703755
231 46943137
496 8790538
186 240642040
864 342830551
113 759629958
608 592553011
188 143648033
256 6936737
160 63334778
285 210211287
40 307784806
362 129521062
612 2996138
76 392895068
77 1000000000
721 577404506
574 245331501
760 232291607
579 1000000000
54 257761306
249 277408741
301 1447966
511 1000000000
500 11960265
437 166316096
747 10487263
307 604339462
39 45220929
582 131424700
743 91394422
105 241390486
795 12310221
157 41547016
167 41122597
856 224329553
448 185312943
588 1000000000
226 148786184
65 619090234
643 34662555
833 579473182
669 55506666
634 34504427
815 2102156
284 503265366
489 104580675
109 58051535
364 134632159
307 39852113
127 141382799
258 2195001
379 254205381
68 202279398
786 314062625
139 220682672
894 256190580
70 497745745
383 341496832
890 420146067
403 213152150
769 295688576
740 548600558
885 974483969
430 106857330
242 18412497
631 530726106
139 773831598
625 335740161
516 287438779
183 117416064
313 23031318
766 7787929
235 673974600
493 649985197
9 123655440
20 161437846
47 494623442
431 5638409
610 53879976
875 3134394
729 113051836
439 34903135
380 1000000000
332 2317612
411 983888511
620 96680521
631 41785971
453 151648836
323 30864910
783 247661284
256 255571497
284 590108
705 341111564
10 635803430
594 98286615
688 378683638
23 108958439
551 141618265
237 15586219
390 98021082
123 202496639
9 1000000000
5 74212930
785 109769760
356 599291866
117 66956800
707 434549992
333 54147442
26 1000000000
525 315570483
78 62661948
678 136450143
38 107911161
431 297873070
798 16869607
880 219262495
167 62045149
2 48739928
548 175210482
636 362970334
229 392807745
558 40376966
462 511828628
841 30878883
712 928513171
124 18036489
810 36482986
55 38010548
549 39032683
835 42982975
627 245718051
643 1000000000
38 17099287
191 1000000000
654 198554140
52 755129974
665 1000000000
876 1000000000
877 1000000000
673 395818308
674 22180454
479 190568233
74 1000000000
125 1000000000
43 157414611
295 141851549
864 137013678
497 1000000000
542 277141577
532 108943112
60 115840515
859 195671376
498 56805872
670 59047293
189 204465546
198 81098976
167 473050543
454 98621654
66 219141024
302 22977015
394 17835947
743 98208459
242 130743556
588 102659341
850 229956239
241 1000000000
474 333039847
698 1000000000
323 531335606
640 9648575
40 103479294
106 219682690
277 94619733
313 93192325
899 133198473
28 1000000000
65 94559637
519 281783847
11 88461793
214 498222810
173 504108394
446 62742350
900 196375056
682 400273775
419 124376463
542 134518333
239 171558681
775 56308995
691 469790715
736 269514595
687 355897948
781 290192315
399 19073669
211 65618124
688 19369847
696 478386480
649 292267405
483 1000000000
142 205333676
217 36425127
484 1000000000
780 29448540
246 850490294
563 60538377
272 490700368
583 60960887
435 1000000000
46 240586032
834 600182340
158 542385182
29 31896206
483 31895628
853 29231582
704 9252846
701 51568056
581 490633514
209 331303516
890 301295806
805 96753741
212 1000000000
114 71618884
378 712884498
715 437505784
480 131683397
41 17570951
514 63971776
150 1000000000
289 22564056
600 1000000000
636 442108221
155 101411475
688 38613800
53 67542895
376 21311397
780 443442919
380 245796347
228 10764406
164 87400617
651 527745547
581 29644327
491 1000000000
570 496206029
815 1000000000
544 238687544
472 22269449
369 6882552
237 92946091
227 131672852
830 214668949
534 141164685
52 393912533
116 285672565
893 351016482
295 307956479
19 270203657
639 258382287
14 234910413
598 4078542
105 396364419
578 48018318
336 340885721
778 41923082
319 5750331
267 127354041
755 127727574
184 305868626
847 115156747
549 427914338
311 54536270
62 59670189
576 746757801
332 60463045
157 19345734
294 1000000000
778 1000000000
128 212291
771 56689374
371 9989643
533 112798205
814 68945946
59 107234017
490 56450540
582 168329441
253 638565281
685 3786746
157 270284404
120 77130385
437 411540696
147 288629560
558 106369174
523 256259212
351 1000000000
215 163333988
624 2551155
451 105996190
362 1000000000
700 12690977
279 134736173
369 1000000000
386 282684484
582 34798507
608 87198555
872 1000000000
311 64564134
202 245846041
430 23420017
284 1000000000
581 52399165
363 285548135
201 891788346
845 109506979
505 161374464
801 471779576
309 327319675
520 1000000000
386 430017175
652 139155536
767 576248300
160 97696868
268 90747982
64 291995114
358 75049372
61 1000000000
812 56411155
254 313840861
870 277157198
72 7736698
672 546429544
413 2951987
227 14489295
803 314013066
310 3687929
118 175290716
350 1000000000
728 136169903
118 46205628
463 146417101
490 63184673
198 1000000000
774 38511490
494 495002719
787 546583691
598 93780957
340 1000000000
466 29316467
97 2845730
510 566976965
507 136026508
795 66734414
797 65720803
132 801293825
331 232885060
526 148752561
514 149432477
688 368781712
809 1000000000
182 58071584
468 1000000000
860 8873205
547 277038420
271 77303911
199 1000000000
858 55748802
7 432520423
845 87430124
216 32499870
357 86776960
196 243993853
836 272168947
666 374721016
453 1000000000
139 126724101
449 27088375
825 4271086
342 39691644
327 47910360
115 62767906
589 237461489
449 1000000000
336 266598372
119 174592404
187 92487240
141 239274938
778 270893039
411 405171649
29 239516719
582 345881678
401 163534288
253 712227375
878 148576902
400 15129558
2 65622884
44 190176937
759 398388426
392 105134034
580 162214164
48 1000000000
502 82196731
189 105932495
627 262527075
54 325968658
817 40663322
355 113133536
76 228231839
245 1000000000
270 1000000000
118 40007817
273 196775775
157 1000000000
413 1000000000
439 131474173
788 562534852
246 26727241
760 26154488
553 30599376
889 633806253
404 258260028
741 50476052
468 91914589
578 332547
372 14384466
203 27841295
853 366808244
557 276295210
277 206014616
331 1000000000
178 418685020
245 72853535
124 111091408
623 30896838
369 33166726
18 441038051
859 23918199
281 502630767
125 128319777
565 1000000000
608 404626159
840 11138579
315 1000000000
836 319391674
286 463653649
617 93806208
273 1125148
365 236930063
85 721790848
790 58895521
109 106089349
700 1000000000
730 1000000000
25 99746241
271 636560314
875 153068381
852 506746585
305 125827303
837 229102130
308 142179500
279 28030381
619 253793127
605 186540750
42 8344229
535 41678247
177 441907929
494 164270057
269 391903002
508 1000000000
613 110227417
408 229643164
165 371212502
603 41704331
442 69470912
379 1000000000
39 12950568
239 284351414
204 334384152
632 294144344
42 1000000000
205 1000000000
248 220097509
394 255576306
586 925626769
107 30502281
513 79719482
889 391736759
324 393141973
687 194197978
275 1000000000
677 493428796
503 305210262
152 98541364
538 847104421
503 89779897
47 171305728
698 1000000000
415 33196078
178 266710774
136 197148591
418 1000000000
377 418228038
550 118265014
722 835879918
3 546739610
336 137212902
135 893908699
750 16906591
281 273792394
540 38255548
570 9806092
179 26667666
292 705807162
506 116866464
714 136503371
69 145266062
760 37027378
825 12755680
643 7698534
697 43629852
202 66401457
69 125875115
530 234305727
305 206756386
169 143731389
58 768227290
825 42915702
499 211703050
622 86402588
77 45350709
314 87843146
119 15787320
455 162165248
861 183220542
244 15700963
599 40688529
510 1000000000
582 36788018
216 55093817
781 184960698
250 71015118
320 244686960
720 335514516
452 122244327
763 249586633
544 1371554
178 125096952
484 410050974
306 574973353
557 335117860
417 16245255
325 120145419
298 66638251
307 25176670
394 88869396
220 193873055
691 3533484
14 59265612
80 318020737
524 89519183
141 812212453
63 21960959
342 1000000000
293 93207875
280 1000000000
744 3205164
443 219694225
68 1014801
377 197097157
204 448399519
740 21623568
704 62665662
771 162275441
384 168813909
171 234910909
345 399772219
39 269079384
866 94788299
475 1000000000
591 600869081
387 234744210
584 194415061
588 34244012
118 14157171
649 150532228
684 99496758
698 238025782
807 639747388
716 1000000000
722 139635912
446 920604280
305 22345964
416 2217266
836 138195889
351 109644273
480 1000000000
218 1000000000
44 210848949
185 567078976
449 121517145
709 1000000000
613 224956375
268 30415704
350 223348915
689 112992074
288 148348334
417 38727696
845 34605229
538 435216442
755 228091772
171 22222681
458 1000000000
688 78687592
84 247681449
570 118474575
311 129695040
784 109493002
614 113431805
527 356784978
14 688917113
885 512551665
870 174878311
240 305996214
602 4803554
31 154769617
134 256017674
391 507448576
651 229013737
3 83125792
656 9039413
599 30413053
30 18576936
452 410285108
791 421460327
329 10991914
481 12957018
118 22915754
596 1000000000
619 44811298
870 198267523
601 741048740
757 1000000000
487 94390614
732 90634746
730 48826540
300 21022282
684 163590432
180 290159715
59 480569225
308 1000000000
331 1000000000
609 162446429
291 210410912
345 1000000000
391 61949637
463 134696794
291 38183807
176 809512521
479 422893075
30 170705316
328 33139172
48 163748281
722 361420955
738 1000000000
455 1000000000
501 45838021
353 1000000000
380 976188431
367 718681600
751 320731326
770 85056350
123 1000000000
36 744540608
755 243973815
264 1000000000
219 892636228
607 41849474
828 104566002
723 1000000000
545 12065866
595 1000000000
830 226484850
35 574198864
863 241516767
364 60995543
101 88161347
509 148370271
515 1000000000
214 40985777
438 1000000000
452 66955594
553 256420770
82 1000000000
736 98564376
380 14332713
515 98291381
170 368378743
475 102283611
349 476495340
651 84699916
817 1440618
231 38837292
432 1000000000
44 82397599
556 58265596
549 913875958
872 90762388
594 111512590
136 1000000000
716 489197072
789 421782450
330 77709124
818 93157809
312 142510795
119 130804687
442 39625006
677 125287225
249 317160559
659 17243766
28 168326422
833 557517453
692 10467561
308 68736203
623 338426013
839 313541351
360 29232382
386 137401122
820 27055040
478 1000000000
673 109153122
138 1000000000
618 54154656
78 100522317
543 35531176
582 149279720
749 20894660
883 44584391
723 9411283
520 280712233
285 111281479
830 166974805
635 14249204
771 51897209
438 261750286
389 155600837
894 406023378
756 105232663
853 1000000000
234 16860902
781 275473753
821 326196
781 794026531
777 285507471
266 411165252
188 344716456
242 84246737
544 21726634
831 393956155
845 61976310
245 323092361
85 50331962
426 43163505
526 659585123
669 146639176
431 84552070
739 268362596
785 199925884
801 123081327
382 59740949
256 344206708
205 33999220
104 32730310
791 73425576
719 277382120
826 712974235
615 141294638
9 545622569
547 1000000000
864 143186707
476 494260427
76 28886449
633 57318613
868 28604893
574 64889525
52 43956710
695 443822538
117 324108278
413 206676900
730 117466695
643 45500592
795 89416916
406 131827715
432 7803580
480 177392178
870 1000000000
355 38504569
68 55647075
755 173360584
291 95788882
362 252816423
162 203651450
546 1000000000
825 481153269
759 557770014
544 253682486
251 31807166
332 337270269
12 1000000000
888 1000000000
17 1000000000
92 72894293
667 25977896
437 94541364
765 163601663
446 1000000000
831 14283703
311 61274740
429 440558759
33 806870809
444 210475584
763 165385389
299 266669242
725 39067037
46 251533361
448 49923923
294 1000000000
751 1000000000
186 22949527
438 151396133
146 126463174
329 243046919
111 192636062
125 533709109
292 928276207
485 160862532
205 319258708
834 23624496
35 83684117
758 791396819
369 117045174
179 19408365
735 1000000000
557 306038197
594 152448607
670 288049382
712 127476945
500 53411744
372 133684478
375 18082957
495 73149672
673 69264240
391 11903437
112 15985489
735 110135100
156 66949080
659 91292496
619 47790
408 47632286
543 25326847
389 2026674
887 1000000000
346 1000000000
368 181885458
372 76441553
212 227623036
794 58487282
446 52146740
156 141242108
15 26465724
139 168344932
105 56175930
34 117273727
139 474111954
413 584215081
597 25032064
888 1000000000
148 113563554
300 7513767
551 235085896
428 368060079
722 1000000000
73 430478375
34 198372161
366 201304595
158 196565037
683 167219686
30 34815196
540 58013440
570 43178985
18 247947274
343 253338413
376 666521119
628 48223920
402 1000000000
398 125649655
629 91575235
160 70681653
656 237822424
442 627305547
811 172997820
796 55247538
747 3224462
11 111548750
142 11787836
522 589108355
719 226598284
657 4264628
431 171113337
765 295358120
380 823975084
65 905708356
573 57819110
297 63334714
727 1000000000
282 425715617
516 1000000000
263 175773849
398 22514404
408 148012715
537 1000000000
354 349828293
444 1000000000
572 126077683
43 56849952
194 19166598
374 340219
340 91037683
586 608732464
711 142436692
838 31158022
10 92109197
110 321840330
410 391150304
514 347871373
777 93337009
739 565910666
373 1000000000
201 49976370
198 171170694
882 930198206
146 257168302
896 9741628
851 315050800
814 367102087
361 295638634
848 18416982
510 28617487
327 598738423
216 243560536
850 116834090
698 24714197
58 7385665
773 281348152
173 176685859
824 58325643
133 307476861
519 69082385
894 105700347
311 2665470
702 64663017
678 109752273
875 27955910
778 5870692
717 37685412
147 97428030
734 465429335
208 64317268
120 5879974
1 124845246
294 29199126
74 329094374
633 1000000000
676 24245943
432 174436592
374 25562826
183 35741285
392 21419560
378 2478316
195 57143643
150 250104510
386 156287457
246 318071808
865 72635422
131 346903640
388 1000000000
659 40412711
508 245887942
316 15807795
356 198987978
570 755260675
717 362721923
415 127112918
218 181971177
9 50838538
831 25180552
647 166936375
156 315780802
734 8954269
350 168396671
101 127242965
252 131854628
736 403956512
110 845661238
488 513393132
537 94277613
247 139333569
312 17532081
696 201929344
611 578155724
780 958750520
811 231443625
489 260303536
307 188272104
510 788701495
635 26785902
363 469876766
676 189786311
553 491762907
193 11454286
555 62189626
122 191334182
537 49402060
643 148503820
124 36340909
29 1000000000
155 290618054
771 409429076
654 50584185
430 183791665
310 556643082
84 56883682
622 1000000000
619 13559973
138 386059097
483 4443205
342 131642302
542 302568064
755 43437128
526 63350657
676 217316277
531 95368306
58 1000000000
103 226036695
44 169291132
700 19480940
94 13388744
481 74434119
756 88758482
375 492552265
835 92328929
801 677992849
158 50047423
507 574199637
781 603782812
414 652226952
869 732348595
120 128473976
237 200957621
223 41628271
685 29776202
7 5857098
498 443395575
747 55932726
671 66761355
807 29100205
804 334261601
343 1000000000
773 375137801
752 407708533
231 40725274
465 39398888
789 255042895
570 651777126
36 72951207
652 188915799
667 64750331
146 155201892
450 320580968
668 16659841
593 8275692
126 199360950
517 393227477
45 236734656
597 5775790
552 503179717
461 82400035
236 1000000000
482 188043430
284 236029147
167 202032426
44 86976245
792 24438830
32 35714518
46 222417691
65 362135806
839 77441579
306 133002608
430 61795539
163 564110205
784 446524
233 1000000000
39 1000000000
243 1000000000
526 1000000000
833 297103158
330 830576578
184 176214388
809 156305747
611 724998390
641 44981849
730 244152125
582 1000000000
190 84714071
439 179319075
469 302799203
664 140257386
310 206248637
801 70797517
110 29427559
407 71363641
159 714367374
56 232154795
792 1000000000
127 17179875
425 218700838
857 1000000000
575 49084631
316 344679038
421 401287710
727 230001928
468 7945471
139 43958644
22 3088253
171 144353803
557 55113598
387 38191541
497 52716759
151 261383474
700 110465710
692 40632745
444 273155456
405 168165836
12 19544227
651 179978262
453 181005574
696 1000000000
526 56797206
350 48034724
895 41202548
289 179008685
300 2228524
31 1000000000
846 7062511
634 56927983
152 362394305
114 419472495
87 336540485
705 153995493
362 327304984
605 32339825
225 797688015
885 127510708
260 190181543
342 299250508
892 392602545
179 70999370
232 89400372
868 104563797
788 1000000000
657 78027886
777 126657896
507 644450192
757 57673989
777 178032788
115 1000000000
503 36180609
444 1000000000
790 71544624
546 216710624
677 168406238
240 188679996
393 31552068
71 168246334
184 1000000000
278 1000000000
160 225961361
817 153545661
36 295225433
876 45343259
797 12037841
20 6356204
586 178620448
756 23500381
611 235391526
56 263257134
125 106349156
481 437895291
82 43149207
442 274112889
817 47481761
699 31976905
107 652024496
369 160868306
62 158765692
499 17032618
101 87222450
677 957147801
264 3588155
68 242238296
424 177659124
58 488562651
152 123504322
730 1000000000
456 203694666
689 12380687
577 16089127
845 265029612
898 157479018
49 350258157
483 9995942
393 1000000000
773 164084354
74 109626815
163 89843411
591 539355881
33 66266586
197 237758531
115 635367364
790 58570078
590 62721180
220 140701755
417 150566315
39 9428480
317 1000000000
213 158962303
289 56644388
20 10139042
189 261189958
627 84812635
569 25800703
467 198706466
682 30027613
471 19199367
583 18114605
355 95285431
744 216264155
399 106342619
102 53732921
156 35683191
576 11795254
749 42042379
610 408914174
175 105246503
117 216831007
473 74359021
420 13980227
203 29628434
231 109119945
821 176448881
630 69659
500 176355673
162 631468492
791 55007834
122 147682127
38 47555198
879 218122450
682 268961638
799 136644839
509 204136296
705 361633639
758 44529437
134 4915280
594 131016776
900 740042779
847 18888498
206 180013562
328 272541437
468 328589179
118 54470924
479 34540319
280 61086621
214 274706908
422 221674587
1 90882080
656 437871781
812 212235516
471 76518235
744 24557386
770 367052799
777 10442637
77 295742578
761 614209900
713 103843242
546 1000000000
893 164070045
483 1000000000
165 6166137
836 145180698
598 366474948
218 39691494
855 51886371
88 1000000000
336 1000000000
715 142820006
458 306643015
465 281223853
819 13812246
880 733896844
22 202007353
92 41577483
144 337753797
127 46790149
483 541608666
539 19874556
566 144346432
264 631630667
405 10762665
772 54021353
497 148994300
561 1000000000
797 343625751
394 61772734
726 346761648
488 55558041
694 154259833
354 1000000000
607 55265444
460 1000000000
45 74530098
606 10553444
510 42380134
33 65946095
508 240765481
260 126991522
314 1000000000
828 112621957
897 431515962
383 160092449
644 208568761
239 254461992
415 17978986
384 139651
274 3169499
828 222839146
102 121645944
661 371909750
642 35620028
610 145640150
743 1000000000
660 42911773
875 60095959
526 64519814
77 381752680
580 77008066
278 1000000000
775 153714994
24 230025183
818 18316981
650 489473827
369 150328993
628 350413791
288 430089609
342 227376057
128 25578289
281 193181140
216 99115814
101 1000000000
164 57547075
260 332284023
113 409337940
40 191550329
58 164666986
20 2591535
155 1000000000
781 369057873
129 101409711
718 11378
299 151109154
739 1715952
177 4213999
452 34242104
852 1000000000
314 34810411
627 71477127
880 209698422
258 133010846
358 277099527
362 33384367
21 214624209
721 707475648
216 5431789
897 304514681
491 84512824
294 507939889
223 58925471
619 57863200
691 284773912
148 90129665
495 44857385
37 69385490
732 25097815
143 63710127
360 397179908
465 276510789
754 1000000000
315 15384817
859 16255797
482 1000000000
181 27582580
693 34069843
355 64921549
352 200224376
321 273220297
456 108749308
740 239978867
772 444680422
891 52644676
704 30371066
39 80059732
760 53101984
154 251234762
93 289872349
686 135416926
666 908016649
422 2054231
188 240746328
459 2198281
298 22787829
528 356969036
396 111068088
869 37158297
446 1000000000
83 126490675
509 155317865
645 143102617
176 373812847
839 455469375
219 95937938
789 374269751
19 613386171
824 103596150
19 68107051
443 587396306
123 168265948
27 192551775
364 457697701
130 92277451
40 48567974
362 35622258
186 3686733
527 1000000000
819 1000000000
432 1000000000
137 2122470
621 118657642
463 304523865
278 8811387
310 274148263
203 5731933
512 1000000000
469 1000000000
839 167026068
788 1000000000
499 1000000000
18 101059870
815 209760597
781 21053473
783 311803937
644 2932696
459 558382976
336 14345408
216 105717892
271 79475828
564 4461243
832 1235990
294 35870172
660 370959216
51 170702344
869 82652199
793 277208048
886 1000000000
795 228119852
399 618044000
570 6905178
573 127608411
505 33916773
191 333859205
792 29539173
725 253906302
747 348051769
416 178627119
867 170086840
163 137896168
323 13261001
102 40799196
712 131158162
625 31524862
872 242942594
85 129118538
485 1000000000
102 307379093
459 156136249
738 608134557
724 113890816
323 96181748
494 268524479
364 3996423
269 379693188
281 1034540
155 171823777
255 1000000000
22 291988795
285 17116354
757 139320296
379 34493315
889 1000000000
2 277666238
357 217899868
125 233827009
773 4611300
76 243952034
653 1000000000
608 54318345
394 737202617
492 50768709
11 69093377
436 321062402
412 204227939
61 613869349
374 46585187
358 86803127
340 363534046
283 133318008
147 472898608
76 199431659
49 209956689
662 917538139
352 69041255
300 131898687
791 43034119
543 316414843
563 283713501
509 279143599
3 503368631
640 257017112
639 93799327
372 37016783
840 1000000000
63 4586722
496 239628127
851 371819330
38 1000000000
780 50504570
403 51051390
788 65840502
369 4401674
617 50982633
687 36560195
271 1000000000
701 336533284
604 68023252
184 35389013
54 1000000000
731 44120221
228 10671039
818 268030604
471 541378710
846 242984243
269 53905036
390 21803668
701 293783286
350 325573079
500 303831497
855 68199734
800 15458643
96 450012956
344 159690254
381 1000000000
280 31847383
790 47224132
725 78034372
68 267724204
786 354633023
98 374162359
543 542865454
897 1000000000
381 2419624
100 708040437
479 347345677
571 350645576
881 211638748
782 27317078
883 179859845
854 112287886
510 75010650
846 203686790
793 249693935
2 3656199
821 1000000000
295 816021402
61 110014048
372 1000000000
501 64506254
605 921122121
145 137362209
19 633673144
2 28707876
257 304966104
407 526403595
479 32919667
88 194904447
417 151267091
794 743705719
296 1000000000
192 211350249
823 636179817
862 61996526
283 164586579
5 1000000000
426 1000000000
608 20010751
859 149515968
555 23952974
779 149275811
35 27937440
828 314472351
659 459142271
529 76401945
607 5637164
490 45935166
211 121765011
44 209357235
352 314161878
666 170202215
345 184238091
728 112201888
167 249240754
830 1000000000
664 636388962
205 29005808
414 126325314
445 20519050
389 397162351
192 1000000000
571 35624776
900 239184681
14 398470675
580 1000000000
506 86793055
621 149790854
149 561654498
205 47102600
325 1000000000
74 81257448
314 161708203
396 337043479
346 617415020
665 524541252
771 112749575
275 62313955
280 64838128
302 310942389
818 48778348
568 7247179
127 144651017
447 1000000000
226 82484654
287 18325341
244 294300826
286 12633292
395 369106726
118 241273637
842 1000000000
602 525290589
229 43227693
867 100605402
381 543140063
44 318861476
645 368824977
265 6658530
285 157903426
654 59283434
642 26353406
160 364380493
739 346176756
506 170333378
412 94180844
101 79838516
325 1000000000
839 1000000000
779 270749635
114 36498981
573 26544903
126 94443762
252 282331126
337 36235212
79 57897263
489 34261739
46 1000000000
290 966920744
17 84413452
814 1000000000
41 24423414
151 1000000000
521 91435950
208 264270549
869 717971486
326 600429047
602 180694024
420 372741409
451 1113324
730 11160280
812 178007134
208 7089041
118 286458652
151 1000000000
528 65028529
810 1000000000
122 6962087
533 1000000000
469 406370108
429 279938132
280 82332030
113 12691251
675 312165175
77 1000000000
62 149816429
154 517667793
310 112226273
275 7034840
698 18439812
804 172980807
159 347883646
354 8865246
39 292774410
708 236002133
352 171927453
694 91308635
246 1569596
257 61382920
59 503926814
175 22259888
285 1000000000
323 135351894
576 68701813
394 177423567
262 154579030
782 317887948
525 227312418
58 1000000000
592 47279042
454 40566610
392 46443984
767 170469011
784 1000000000
100 29937693
348 14215492
409 273280581
729 85884365
247 420600865
517 69805889
897 1000000000
530 82964928
7 24456578
468 32647316
214 141866508
170 288711797
493 264998036
764 151150403
28 182999644
490 79766440
11 289225631
657 281689433
639 826780302
476 459744521
543 104183512
195 506136057
12 691817615
615 285013610
541 291073854
111 586406891
86 104177534
187 395324228
815 770920834
139 104692072
889 642619104
780 80654860
151 20782210
737 149059140
169 27873144
331 184168910
232 10848800
157 174863177
107 111365078
723 48363819
254 137755446
509 167970493
10 216937598
696 259719953
757 8185982
95 193851457
618 1000000000
274 43506888
578 120595582
386 477739365
639 173167957
462 73808972
4 264818787
738 49747156
522 136308977
159 44521601
747 21160580
76 51525824
893 133377043
713 121173747
8 66559600
35 197051776
27 124566758
269 51036215
818 296159778
523 63895529
333 607644685
877 658746680
309 87981598
512 179141203
477 534266367
855 23990722
665 12363967
675 81457364
485 1000000000
238 180198125
662 284491712
118 439391250
131 85668559
807 23002561
753 85990653
895 16686950
343 268077835
660 38598865
445 89184222
178 13249287
359 4652081
487 20510504
710 470291397
145 163792039
209 489902202
147 38684323
285 94720949
94 700350576
40 54764902
81 371832464
736 306555410
28 28325561
233 823184853
584 78230694
521 392172698
879 329040272
266 199496322
447 227563500
620 446205181
204 272579126
793 935051
605 7658159
583 341707512
346 547334212
457 1000000000
459 16954409
568 110390
745 11457671
379 298780779
323 48337673
354 589670264
809 127376028
505 36703380
368 1000000000
333 219972500
439 1000000000
681 161775968
662 39041520
557 405928481
413 154019199
706 493620901
493 1000000000
615 40298556
521 384021823
433 45859393
710 157986660
458 155707854
687 13022629
272 140170645
188 52988910
614 1000000000
861 231318391
129 990041328
607 56713108
292 34199362
193 377269831
135 63500289
175 87445045
259 65390496
774 339284926
790 609934217
417 149304816
27 145350525
712 130064236
495 84670969
664 450824098
396 1000000000
844 221944103
501 122975794
152 233780683
2 113769658
873 789652845
360 13400985
809 184215521
638 33601525
403 71999825
576 35516533
208 207348036
367 259250178
670 1000000000
282 1000000000
692 529602236
773 161800751
351 1000000000
573 320454481
121 102058520
69 16976689
400 585693094
633 359882453
212 292246690
265 156074463
423 380939214
230 1000000000
763 194980356
783 1000000000
692 247839744
449 2767454
152 126619702
539 123734619
189 189251583
365 99626388
146 76990722
875 731250226
700 99675055
246 176878605
242 73146123
665 26249181
476 841141579
112 274285730
230 65633535
324 98801849
461 119849575
28 120397227
672 124410070
176 16433115
804 156048149
585 152164700
32 20928847
754 1000000000
288 106177040
519 10326059
224 21666455
324 8675179
425 880757104
782 96323721
858 208882513
168 578124041
535 5897944
651 16793784
793 4840042
805 82286586
658 1000000000
449 1000000000
377 1000000000
116 193615720
623 1000000000
168 1000000000
366 102221802
48 61561503
637 1000000000
816 39621647
305 462630237
889 160026739
693 667480188
146 21029723
253 12930896
863 76684306
261 843359476
412 9185453
294 533350570
134 31593395
371 28518516
761 1000000000
240 16669703
119 554934245
562 594925074
250 1000000000
416 44020628
473 11902657
610 295002428
189 276658186
93 24491001
768 68141507
16 183029650
396 75627441
683 1000000000
225 1000000000
379 59938147
645 224616100
190 39624672
267 236676565
255 88577592
4 1000000000
747 143205279
217 1000000000
372 334176143
591 3912767
305 553682822
358 272003952
770 275630946
412 728998544
148 48153529
563 130582989
194 688783501
338 64813804
217 687685453
334 601208906
467 158738711
514 193349041
766 642307615
454 272375507
806 13261097
34 123999991
341 257790581
715 227820430
341 163051111
600 179445889
593 23194851
74 3284767
342 73224365
191 15386399
451 582034422
121 27070456
424 210125483
444 152701906
185 1000000000
494 53759258
331 1000000000
81 181198225
289 23209784
349 839520021
188 370347898
864 25638251
39 91314833
796 4478527
642 20537869
212 1488955
257 85442769
853 56049344
413 1000000000
802 116677700
737 512722405
191 181177705
761 171758258
780 244899422
142 114020313
786 199351762
78 124188458
796 60181310
852 12761208
354 48440310
873 359494469
517 22197519
195 300609768
128 1000000000
469 9562618
399 59015843
148 88963124
855 113531649
871 20769220
635 413459576
574 90033707
99 1000000000
561 42285682
720 2776814
737 522052898
889 683540444
497 9837714
486 1000000000
49 550407089
420 811784709
326 96228919
321 233463026
187 385352902
340 1000000000
40 168613179
846 215871326
622 613053
37 102368022
364 389761305
296 234355123
550 447366844
375 48451277
241 665018410
611 199582162
683 3788763
663 106578358
551 439854345
543 207123500
478 1000000000
356 419269035
606 772029422
137 13832276
150 1000000000
774 122224238
298 2633047
364 5638165
467 274793011
666 5577417
880 629961536
156 18907933
534 169941265
38 80779649
383 832203083
637 104632036
541 894309868
592 279432477
880 118234144
380 128370392
810 381906349
836 1000000000
69 339910580
112 515135961
384 59000286
520 255345736
340 1000000000
305 170859318
460 11224570
818 1000000000
448 354697507
535 312718088
396 6044595
37 22954666
193 45691326
3 490520857
514 81466563
153 1000000000
736 26917599
408 1000000000
217 739960975
38 252421958
140 77150421
534 462244883
454 597939786
661 7429784
585 170690331
769 4170829
360 424498689
497 117436037
519 98118190
510 29538300
42 74930827
230 170093006
682 49108753
691 581916
131 608764769
565 381145430
691 212432175
563 406791
560 21561505
609 421293
177 28985662
391 301431288
623 106778597
718 175442636
393 1000000000
721 69784479
811 417032601
868 171072719
485 31690037
195 31992884
896 439900286
519 158366972
83 886626937
839 24031395
282 186893711
540 49733460
546 528098637
325 270558888
174 32934690
866 5250096
346 132606694
263 74516006
591 84431213
185 118595617
776 103091357
267 5250607
277 15930623
778 469395762
615 438451359
308 123880362
84 1000000000
19 1000000000
459 49408315
215 923840586
429 87048649
6 9465968
864 129543651
702 105473657
147 105461577
547 83121666
778 733776507
7 32016214
170 714129917
640 231978023
650 101777300
865 576312962
551 621691289
507 226499144
651 408075608
325 479762739
892 291959813
571 176533943
870 18127801
237 274880046
587 124969668
212 36391110
125 74445163
143 136109242
771 135037077
739 61187164
858 149470650
774 174640686
113 64706539
106 1000000000
460 55150643
315 39064770
235 222659118
811 15510642
43 561307955
208 15425044
419 260467713
677 323891760
436 197993612
875 306174478
200 75762973
253 277835481
101 52933285
899 310519757
771 1000000000
858 586890578
201 48296681
20 704873028
243 13603000
748 65813964
289 258286931
99 588134145
579 415859626
731 223098470
434 1000000000
807 300514919
478 141446542
231 1000000000
393 60613236
752 199239699
193 94129089
513 140163118
225 1000000000
174 521362119
42 6669545
328 93385006
394 117850076
358 1000000000
204 216572306
300 953420525
733 532901825
307 25462238
319 356429653
22 75622243
501 86297289
721 195670790
163 385342703
88 257919042
366 640162787
100 92257449
857 103716305
60 395070299
804 470509746
233 591317392
656 321895500
166 643936024
172 278836808
827 54650009
120 1000000000
680 1000000000
136 263479235
482 371290829
185 554360060
712 208196615
715 1000000000
878 29948067
164 26586238
889 578039111
562 598654728
880 125222854
16 2762355
635 360244570
358 583728387
515 84742805
893 1010358
819 39158181
788 923991218
455 220423524
836 193128112
839 111748826
615 246619190
528 23909602
139 737035930
833 257290247
435 92731174
271 17911574
616 3347576
469 266399978
125 8089850
359 531483413
642 20803866
833 11822576
36 1000000000
520 162588910
90 76630559
375 163083644
548 619156950
74 137124074
286 75928213
530 46770746
5 223050155
874 71381932
564 424467344
566 652187410
144 115387736
186 38595963
851 121187747
287 144166485
859 9130118
853 26550288
892 2859783
166 236159471
744 331096319
844 212397925
753 1000000000
374 532819621
823 448923325
617 28858765
32 1000000000
379 127527569
766 315570091
94 117062952
657 297554540
82 1000000000
615 1000000000
38 253653864
526 14137173
398 683429731
837 513965162
446 1000000000
41 20631927
787 255044608
420 288163692
235 154859562
789 427150894
101 7965594
89 17521518
110 489035220
410 24550650
784 434185127
691 117512479
810 295668408
156 96207904
497 5584482
110 571400667
880 35458869
832 78847232
3 579171296
182 21373628
230 232150420
861 176618122
886 196187443
576 80152608
602 408562558
695 5122728
887 1832930
22 421723974
343 303581782
454 470990828
784 116702127
522 54509585
726 94563656
583 243022990
707 47672813
216 115298011
757 23400239
877 173552532
560 254367425
734 12846909
774 314830061
424 585167535
433 261255475
166 93769561
104 222175627
760 16545922
880 17675555
623 35978540
864 124632152
442 3763152
96 6218137
817 339706475
324 69477869
357 134435212
573 122922110
173 300054722
106 1000000000
225 1000000000
847 100879559
110 328777883
461 1000000000
391 742721496
275 67576885
460 1000000000
826 1000000000
173 309560059
196 87512913
727 32911882
655 236835828
537 90996689
290 213222356
752 16062907
782 525378819
826 54153562
726 6143811
789 16056346
122 158076586
485 133252333
135 81808535
260 267538299
707 983939874
564 293243170
321 335788430
57 126899357
682 40295195
157 512525633
804 17147201
46 22917658
766 238685830
208 213111201
820 127226079
781 535643204
863 1000000000
607 492372184
818 1000000000
565 13385915
449 17289096
288 335461953
241 1000000000
78 106717530
661 5687223
138 352358116
209 12324955
825 190437435
838 94582932
261 29715766
31 82237937
297 276759175
472 332050231
485 508448850
341 1000000000
678 587366773
463 124402344
639 1000000000
685 67862015
420 10999720
892 669452669
34 22863
599 127560609
32 275413824
30 10160401
862 349061592
61 101767826
796 218808001
673 257388216
35 393894128
89 633206517
782 269012843
681 761277807
778 26718670
334 123579022
838 395735490
307 46123542
718 301135218
520 24641990
698 20400655
666 183271393
615 27193094
31 1000000000
856 74259122
330 255540738
533 444443467
32 72988806
435 58398604
447 157667475
193 346313334
622 1000000000
483 89625615
38 568610364
814 324469094
561 219386692
661 271188523
406 69396755
788 28606650
782 236137837
548 97091104
511 139829204
748 143593767
516 4324461
380 22456620
873 43934645
684 110024656
135 5152335
497 365518927
257 123511896
758 1000000000
7 25779096
836 44669819
753 65238947
517 6816124
416 85776341
563 222387439
808 1000000000
130 1000000000
387 59746754
292 256992368
299 25428991
591 328601897
219 276363365
195 62570642
407 155178454
150 106293832
228 60047797
178 164340337
653 156985828
694 392174301
527 20161054
175 223785082
484 11714444
524 218397301
414 127795042
709 239596763
493 3400235
275 1000000000
499 37779726
444 45868576
586 620767970
730 46332838
50 82657195
705 140981971
725 112849608
396 104482870
161 1358933
263 994148281
297 113928720
166 336235058
434 1000000000
862 478159915
415 437320763
138 36663380
280 804591550
678 150602079
777 373034656
743 62542994
719 1000000000
340 929145673
361 742869498
565 166241299
424 91948834
222 1000000000
742 26032876
264 14396984
413 1000000000
698 1000000000
877 89161551
173 115231343
380 250439212
96 113959470
336 233341448
643 605381511
264 2571781
698 48194611
205 1000000000
618 18304986
762 5476094
114 192897670
99 1602460
478 65384949
45 98498941
771 529198416
83 59999557
476 39285080
105 944369584
845 154484684
363 481279303
47 724187142
854 92232992
777 39389249
17 268385572
311 40755788
872 199543508
110 503481637
24 68332583
861 166969614
468 220685802
828 290595340
532 243999129
559 1000000000
397 283908614
831 1955064
354 86509480
583 826859820
31 235606019
64 159097735
733 682757406
4 838577346
599 243754849
13 412370944
645 195555253
435 285280375
136 1000000000
860 1000000000
442 638182983
450 403338259
865 335961184
457 87221724
737 70124079
607 13233584
177 45019778
794 138596181
281 692245600
185 45765984
153 130211295
737 57102126
138 401406260
625 9304641
719 113463505
721 835052182
156 108666649
362 90253594
402 371369782
834 443201191
220 74184976
575 185694682
302 46941230
489 212277613
357 1000000000
283 1000000000
480 185656486
693 1000000000
183 754365335
403 25333325
794 11672275
570 75800575
610 223108522
693 592383617
298 201610892
40 23429455
587 380376328
360 296242204
244 381297862
232 287534794
397 290774855
820 731150324
346 832278940
552 2106406
12 210700008
713 1000000000
554 341531905
438 1000000000
56 113919225
320 41368483
751 208388582
646 275445910
878 347116250
492 258287267
265 9062377
714 1000000000
653 715395561
49 89985692
60 133307360
632 73411003
533 1000000000
647 1000000000
289 47398746
159 363067148
698 338508394
127 65133689
755 142217133
851 94552259
333 156890310
424 342264302
714 138412798
253 8234342
8 77846348
594 250246370
559 567118488
104 1000000000
658 25652362
294 398153390
857 279907621
340 3053400
292 64687669
646 2254672
128 435443182
273 258496400
587 276004884
716 31823297
268 245485185
96 98275868
892 161804015
167 175897067
121 7380942
863 102027031
166 1000000000
116 33484223
684 656759541
416 166299785
682 54115608
1 79953887
888 107453579
103 127853755
822 99816984
48 691053300
741 468487694
122 489511744
416 123751255
708 994308351
400 734884463
867 602535385
327 3045612
834 1000000000
839 714896597
337 131177636
384 13642665
868 964131083
460 41602677
340 2772637
33 202950853
616 228480775
67 154510378
649 232007820
476 477637935
778 98535697
738 224256764
267 592427395
164 163199197
384 143733377
651 185322252
390 263984490
10 886187760
704 384144238
629 446254659
374 38499917
212 147649560
133 102775438
404 14079444
531 62254812
652 1000000000
427 8184276
520 72176871
390 906846896
769 79828029
10 18149640
538 119870481
682 43856387
384 95545768
131 117726502
21 194378484
320 18571636
331 1000000000
441 105578288
685 91353496
94 251898194
800 247691501
892 55249558
71 1000000000
390 562007116
546 22889460
236 390568347
302 37099331
491 209687881
561 13236350
842 19550525
414 430893334
293 393017677
818 167828585
625 0
739 121289725
265 1000000000
656 214392462
57 115080074
61 122537861
190 32530066
71 1000000000
50 1000000000
197 379146
688 181051722
615 272620664
457 21769700
146 133903044
519 193682949
373 38752222
249 158077974
540 98110503
135 299405431
580 50663033
554 717419598
484 23494861
665 145584316
700 11050623
329 332210426
624 739953044
368 72017451
65 1000000000
216 100094797
750 131903235
549 1000000000
360 144261762
101 1000000000
606 225401934
266 46855241
136 17546335
87 274349839
626 179697885
77 193081473
617 237436525
843 33634208
8 81529526
553 71247817
223 428740702
619 88164379
303 178388642
274 225968092
455 112670201
897 156709542
883 1000000000
441 82617052
768 226130623
133 1000000000
853 1000000000
725 53418344
302 56253090
685 1373576
467 23682481
486 95126348
809 1000000000
391 16182531
11 494637678
564 627957180
338 1000000000
82 21136553
560 145974167
851 22818349
64 185441201
570 67938824
879 147663270
644 170906504
571 106834602
479 188720119
355 165279296
838 549686303
331 77723421
842 43708680
88 750930718
414 643672442
613 76308475
570 191544554
42 1000000000
14 31456992
219 185812229
647 35737851
65 30653167
464 30073721
664 501897888
365 40263583
798 361435202
379 78720883
85 393390653
629 10367713
436 8180620
339 445277160
100 81136993
538 33576938
167 518461022
281 70234071
99 49762959
656 94130230
400 10409893
580 257653174
484 521807743
867 118676121
417 1000000000
144 171038764
611 30646359
428 33265982
900 256532367
737 50381705
338 92791634
818 54251006
589 221904715
323 906061304
491 83633550
649 279023066
134 50904901
23 1480900
429 395259292
598 128355295
789 65826661
296 231965524
77 513648289
123 124789906
145 229196264
603 318978
89 637086610
22 60809169
842 64297724
826 40683156
443 39056932
714 435125834
353 1000000000
751 1000000000
602 141415365
852 586686044
424 8327893
69 1000000000
267 794766139
110 1000000000
57 92312103
756 587738
752 203362487
362 32359011
748 920988224
653 133367455
131 67418352
671 63643872
795 180346430
703 1101133
491 127161433
574 67330901
472 64939479
566 4964034
385 45172598
722 393642039
798 101984066
362 139270209
63 572857491
718 37457545
601 660395825
215 47444130
343 115874656
581 1000000000
841 250608773
518 119482668
576 606644784
156 81246235
487 28850270
710 550894955
738 246773895
709 48540567
50 51425910
428 63348632
646 66958996
483 22164380
126 233491439
818 8274869
67 251989
522 244314602
292 19493771
198 97426110
841 172591082
298 391747311
251 1000000000
603 2150392
140 12877585
424 1000000000
839 140413752
713 820524833
265 60930193
231 1000000000
4 199914468
301 1000000000
507 61166280
627 138786943
510 111686312
522 124844792
2 16289932
68 72376969
274 45897379
16 910119133
262 249576949
287 81140078
231 204402183
439 293804922
380 121230487
639 728714695
165 129557062
311 349673393
899 127081568
540 39718009
713 7609100
281 601868597
699 5334350
831 1000000000
21 626742198
828 830375865
168 53079776
18 1000000000
759 174143877
337 31428612
887 392093851
467 239684174
395 222630936
446 246150066
491 156599737